【CODECHEF】Chef and Churus（分块）
发布时间
阅读量：
阅读量
有一个长度为n的数组A和n个区间[li,ri]，有q次操作：
1 x y：把ax改成y
2 x y：求第l个区间到第r个区间的区间和的和。
n,q≤10^5,ai≤10^9
首先，修改一个数肯定会改变区间和以及区间和的和，q≤10^5,应该是要在sqrt(n)或logn完成修改操作，查询操作也是如此。
想到了分块。
数组分块，记录每一个点在该块的前缀和（求块的前缀和时用到），记录每一个块的前缀和（有利于询问在求区间和时用到）。
同时，区间也是同样的分块。对于每一个区间块，用差分的思想，求出dev[i][j],表示在第i个块中，aj出现了多少次（有利于求区间块的和），sum[i],表示区间块的和。
for(int i=1;i<=num;i++)
{
for(int j=L[i];j<=R[i];j++)
{
dev[i][x[j]]++;
dev[i][y[j]+1]--;
}
for(int j=1;j<=n;j++)
{
dev[i][j]+=dev[i][j-1];
sum[i]+=1ull*dev[i][j]*a[j];
}
}这些量之所以这么设，在于修改时都可以在O(sqrt(n))下修改。
void change(int l,int k)
{
int ll=belong[l],ee=a[l];
a[l]=k;
for(int i=l;i<=R[ll];i++)
{
if(i==L[ll])
{
s[i]=a[i];
continue;
}
s[i]=s[i-1]+a[i];
}
for(int i=ll;i<=num;i++)
{
S[i]+=(a[l]-ee);
}
for(int i=1;i<=num;i++)
{
sum[i]+=1ll*dev[i][l]*(a[l]-ee);
}
}然后就是分块的基本操作了。已知这些量能够用O(sqrt(n))的时间复杂度计算出来。（需要注意的是答案可能会溢出long long类型，请确保在程序实现时使用unsigned long long类型来存储答案）
unsigned long long get_sum(int l,int r)//add(i,j)表示ai到aj的和
{
int ll=belong[l],rr=belong[r];
unsigned long long ans=0;
if(ll==rr)
{
for(int i=l;i<=r;i++)
{
ans+=add(x[i],y[i]);
}
}else{
for(int i=l;i<=R[ll];i++)
{
ans+=add(x[i],y[i]);
}
for(int i=L[rr];i<=r;i++)
{
ans+=add(x[i],y[i]);
}
for(int i=ll+1;i<rr;i++)
{
ans+=sum[i];
}
}
return ans;
}在编写add函数时，请注意以下事项：如果变量i位于一个块的起始位置，则直接相减可能导致越界情况，请特别注意这种情况； 这个问题长时间困扰着我们
long long add(int l,int r)
{
int ll=belong[l],rr=belong[r];
long long ans=0;
if(ll==rr)
{
ans=s[r]-(l==L[ll]?0:s[l-1]);
}else{
ans=s[r]+s[R[ll]]-(l==L[ll]?0:s[l-1])+S[rr-1]-S[ll];
}
return ans;
}为了方便写，可以把每一个块的L,R预处理出来。
全部评论 (0)
还没有任何评论哟~