需求:区间更新,区间求和。
#include <algorithm> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <map> #include <set> #include <list> #include <stack> #include <queue> #include <deque> #include <vector> #include <string> #include <bitset> #include <memory> #include <complex> #include <numeric> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <time.h> #include <ctype.h> #include <locale.h> using namespace std; #pragma pack(4) const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x7f7f7f7f; const __int64 INF = 0x7f7f7f7f7f7f7f7fll; #define loop(a,n) \ for(int i=0;n>i;i++) \ cout<<a[i]<<(i!=n-1?' ':'\n') #define loop2(a,n,m) \ for(int i=0;n>i;i++) \ for(int j=0;m>j;j++) \ cout<<a[i][j]<<(j!=m-1?' ':'\n') #define at(a,i) ((a)&(1<<(i))) #define nt(a,i) ((a)^(1<<(i))) #define set1(a,i) ((a)|(1<<(i))) #define set0(a,i) ((a)&(~(1<<(i)))) #define gret(a,b) (((a)-(b))>eps) #define less(a,b) (((b)-(a))>eps) #define greq(a,b) (((a)-(b))>-eps) #define leeq(a,b) (((b)-(a))>-eps) #define equl(a,b) (fabs((a)-(b))<eps) #define lmax(a,b) ((a)>(b)?(a):(b)) #define lmin(a,b) ((a)<(b)?(a):(b)) #define fmax(a,b) (gret(a,b)?(a):(b)) #define fmin(a,b) (less(a,b)?(a):(b)) const int MAXV = 100002; #define lc(i) ((i)<<1) #define rc(i) ((i)<<1|1) char o; __int64 n,m,u,v,w,sum[MAXV<<2],lazy[MAXV<<2]; void down(__int64 i,__int64 n) { lazy[lc(i)]+=lazy[i]; lazy[rc(i)]+=lazy[i]; sum[lc(i)]+=(lazy[i]*(n-(n>>1))); sum[rc(i)]+=(lazy[i]*(n>>1)); lazy[i]=0; } void change(__int64 x,__int64 y,__int64 w,__int64 l=1,__int64 r=n,__int64 i=1) { if(x<=l&&r<=y) { lazy[i]+=w; sum[i]+=w*(r-l+1); } else { if(lazy[i]) down(i,r-l+1); if(x<=(l+r)/2) change(x,y,w,l,(l+r)/2,lc(i)); if((l+r)/2<y) change(x,y,w,(l+r)/2+1,r,rc(i)); sum[i]=sum[lc(i)]+sum[rc(i)]; } } __int64 query(__int64 x,__int64 y,__int64 l=1,__int64 r=n,__int64 i=1) { if(x<=l&&r<=y) return sum[i]; else { if(lazy[i]) down(i,r-l+1); __int64 cnt=0; if(x<=(l+r)/2) cnt+=query(x,y,l,(l+r)/2,lc(i)); if((l+r)/2<y) cnt+=query(x,y,(l+r)/2+1,r,rc(i)); return cnt; } } int main() { #ifndef ONLINE_JUDGE freopen("A Simple Problem with Integers.txt","r",stdin); #endif while(scanf("%I64d %I64d",&n,&m)!=EOF) { memset(sum,0,sizeof(sum)); memset(lazy,0,sizeof(lazy)); for(__int64 i=1;n>=i;i++) { scanf("%I64d",&w); change(i,i,w); } for(__int64 i=1;m>=i;i++) { getchar(); scanf("%c",&o); if(o=='Q') { scanf("%I64d %I64d",&u,&v); printf("%I64d\n",query(u,v)); } else if(o=='C') { scanf("%I64d %I64d %I64d",&u,&v,&w); change(u,v,w); } } } return 0; }