题目链接：点击查看
题目大意：给出一个长度为 n 的数列，再给出 m 次操作，每次操作分为两种情况：
C l r d：区间 [ l , r ] 内的数字都加上 d Q l r ：查询 [ l , r ] 内的区间和
题目分析：分块的做法比较直观，将长度为 n 的数列分为 sqrt( n ) 个长度为 sqrt( n ) 的独立部分，对于查询和修改：
如果 l 和 r 位于同一个部分内，则直接遍历即可如果 l 和 r 位于不同的部分内：记 ll 和 rr 分别为第几个部分 遍历 [ ll + 1 , rr - 1 ] 的每个部分，给 add 数组加上 val * ( 每个部分的长度 )对于两头多出的部分，直接遍历即可
时间复杂度 ( n + m ) * sqrt( n )
代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int n,m,t,L[N],R[N],pos[N];LL a[N],sum[N],add[N];void update(int l,int r,int val)
{int ll=pos[l],rr=pos[r];if(ll==rr){for(int i=l;i<=r;i++)a[i]+=val;sum[ll]+=val*(r-l+1);}else{for(int i=ll+1;i<=rr-1;i++)add[i]+=val;for(int i=l;i<=R[ll];i++)a[i]+=val;sum[ll]+=(R[ll]-l+1)*val;for(int i=L[rr];i<=r;i++)a[i]+=val;sum[rr]+=(r-L[rr]+1)*val;}
}LL query(int l,int r)
{int ll=pos[l],rr=pos[r];LL ans=0;if(ll==rr){for(int i=l;i<=r;i++)ans+=a[i];ans+=(r-l+1)*add[ll];}else{for(int i=ll+1;i<=rr-1;i++)ans+=sum[i]+add[i]*(R[i]-L[i]+1);for(int i=l;i<=R[ll];i++)ans+=a[i];ans+=(R[ll]-l+1)*add[ll];for(int i=L[rr];i<=r;i++)ans+=a[i];ans+=(r-L[rr]+1)*add[rr];}return ans;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",a+i);t=sqrt(n);for(int i=1;i<=t;i++){L[i]=(i-1)*sqrt(n)+1;R[i]=i*sqrt(n);}if(R[t]<n){t++;L[t]=R[t-1]+1;R[t]=n;}for(int i=1;i<=t;i++)for(int j=L[i];j<=R[i];j++){pos[j]=i;sum[i]+=a[j];}while(m--){char op[5];scanf("%s",op);if(op[0]=='C'){int l,r,val;scanf("%d%d%d",&l,&r,&val);update(l,r,val);}else{int l,r;scanf("%d%d",&l,&r);printf("%lld\n",query(l,r));}}return 0;
}
总结
以上是生活随笔为你收集整理的POJ - 3468 A Simple Problem with Integers(分块)的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
