「codechefFNCS」Chef and Churu

2014年12月18日4,1771

题解

分块水过

将函数分块，每一块大小√n，预处理一块内的函数统计每一个数字的次数，以及这一块的答案

这一部分n√n

并用树状数组维护a的前缀和，线段树呵呵。。。

对于询问

将整块的答案加起来，其余部分的每个函数在树状数组中查询

对于修改

修改树状数组

依照每一个数字在每一块的次数，更新每一块的答案

这一部分n√nlogn

若理论分析似乎分块设小会更优，但若考虑下常数会发现好像并不会。。。

注意本题要用unsigned long long

还有一个很牛逼的重建分块做法

每√n次操作重建a并维护f的前缀和

每次询问分两部分计算答案

一个是不在块内的修改，由于我们得出F前缀和，这部分就是O1了

在块内的修改，我们把一块内的询问都拆成两个1-x

然后对于每一块，从左到右扫F

维护就是1到当前的F，对于每个位置的答案计算次数

每添加一个F，就相当于把一段的答案计算次数+1

用分块可以做到√n修改，每一块内修改次数是n

块内在这个询问前的修改只有√n个，每个查询只要O1

复杂度是n√n

n√nlogn 分块

#include<cstdio>
#include<cmath>
#include<iostream>
#define ll unsigned long long
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
ll ans[505],t[100005];
int n,q,blo,cnt;
int bl[505],l[505],r[505];
int c[505][100005];
ll a[100005];
int S[100005],T[100005];
void add(int x,int val)
{
	for(int i=x;i<=n;i+=i&-i)
		t[i]+=val;
}
ll query(int x)
{
	ll tmp=0;
	for(int i=x;i;i-=i&-i)
		tmp+=t[i];
	return tmp;
}
void insert(int t)
{
	add(S[t],1);add(T[t]+1,-1);
}
void del(int t)
{
	add(S[t],-1);add(T[t]+1,1);
}
void pre()
{
	for(int i=1;i<=cnt;i++)
	{
		for(int j=l[i];j<=r[i];j++)
			insert(j);
		for(int j=1;j<=n;j++)
		{
			c[i][j]=query(j);
			ans[i]+=a[j]*c[i][j];
		}
		for(int j=l[i];j<=r[i];j++)
			del(j);
	}
}
ll query(int x,int y)
{
	ll tmp=0;
	int L=bl[x],R=bl[y];
	for(int i=L+1;i<R;i++)
		tmp+=ans[i];
	if(bl[x]==bl[y])
		for(int i=x;i<=y;i++)
			tmp+=query(T[i])-query(S[i]-1);
	else 
	{
		for(int i=x;i<=r[L];i++)
			tmp+=query(T[i])-query(S[i]-1);
		for(int i=l[R];i<=y;i++)
			tmp+=query(T[i])-query(S[i]-1);
	}
	return tmp;
}
int main()
{
	n=read();
	blo=sqrt(n);
	cnt=n/blo+(n%blo!=0);
	for(int i=1;i<=n;i++)
	{
		bl[i]=(i-1)/blo+1;
		if(!l[bl[i]])l[bl[i]]=i;
		r[bl[i]]=i;
	}
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)
		S[i]=read(),T[i]=read();
	pre();
	for(int i=1;i<=n;i++)add(i,a[i]);
	q=read();
	while(q--)
	{
		int opt=read(),x=read(),y=read();
		if(opt==1)
		{
			add(x,y-a[x]);
			for(int i=1;i<=cnt;i++)
				ans[i]+=c[i][x]*(y-a[x]);
			a[x]=y;
		}
		else 
			printf("%llu\n",query(x,y));
	}
	return 0;
}

100

101

102

103

#include<cstdio>

#include<cmath>

#include<iostream>

#define ll unsigned long long

using namespace std;

inline int read()

{

int x=0;char ch=getchar();

while(ch>'9'||ch<'0')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

ll ans[505],t[100005];

int n,q,blo,cnt;

int bl[505],l[505],r[505];

int c[505][100005];

ll a[100005];

int S[100005],T[100005];

void add(int x,int val)

{

for(int i=x;i<=n;i+=i&-i)

t[i]+=val;

}

ll query(int x)

{

ll tmp=0;

for(int i=x;i;i-=i&-i)

tmp+=t[i];

return tmp;

}

void insert(int t)

{

add(S[t],1);add(T[t]+1,-1);

}

void del(int t)

{

add(S[t],-1);add(T[t]+1,1);

}

void pre()

{

for(int i=1;i<=cnt;i++)

{

for(int j=l[i];j<=r[i];j++)

insert(j);

for(int j=1;j<=n;j++)

{

c[i][j]=query(j);

ans[i]+=a[j]*c[i][j];

}

for(int j=l[i];j<=r[i];j++)

del(j);

}

ll query(int x,int y)

{

ll tmp=0;

int L=bl[x],R=bl[y];

for(int i=L+1;i<R;i++)

tmp+=ans[i];

if(bl[x]==bl[y])

for(int i=x;i<=y;i++)

tmp+=query(T[i])-query(S[i]-1);

else

{

for(int i=x;i<=r[L];i++)

tmp+=query(T[i])-query(S[i]-1);

for(int i=l[R];i<=y;i++)

tmp+=query(T[i])-query(S[i]-1);

}

return tmp;

}

int main()

{

n=read();

blo=sqrt(n);

cnt=n/blo+(n%blo!=0);

for(int i=1;i<=n;i++)

{

bl[i]=(i-1)/blo+1;

if(!l[bl[i]])l[bl[i]]=i;

r[bl[i]]=i;

}

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=n;i++)

S[i]=read(),T[i]=read();

pre();

for(int i=1;i<=n;i++)add(i,a[i]);

q=read();

while(q--)

{

int opt=read(),x=read(),y=read();

if(opt==1)

{

add(x,y-a[x]);

for(int i=1;i<=cnt;i++)

ans[i]+=c[i][x]*(y-a[x]);

a[x]=y;

}

else

printf("%llu\n",query(x,y));

}

return 0;

}

« 「BZOJ3790」神奇项链「BZOJ3809」Gty的二逼妹子序列 »

Steven_Meng

好像您的代码有点问题，交到上面只有10分

hzwer.com _ Home | http://hzwer.com

「codechefFNCS」Chef and Churu

分类目录

热门文章

Myfriends

近期评论