这个题意思是输入m,n,m个数,n个询问
然后Q是查询区间数的总和
C是把区间内所有值加上一个数
这个题要用到延迟标记：
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> using namespace std; long long a[100010],tree[100010<<2],yan[100010<<2];//a是数,tree是树上的节点,yan是延迟标记 void create(long long h,long long s,long long e){//建树 yan[h]=0; if(s==e){ tree[h]=a[s]; return; } long long mid=(s+e)/2; create(h*2,s,mid); create(h*2+1,mid+1,e); tree[h]=tree[h*2]+tree[h*2+1]; } void change(long long h,long long s,long long e,long long x,long long y,long long z){//h为当前节点 if(s==x&&e==y){ yan[h]+=z; return; } tree[h]+=(y-x+1)*z; long long mid=(s+e)/2; if(x>mid)change(h*2+1,mid+1,e,x,y,z); else if(y<=mid)change(h*2,s,mid,x,y,z); else{ change(h*2,s,mid,x,mid,z); change(h*2+1,mid+1,e,mid+1,y,z); } } long long chaxun(long long h,long long s,long long e,long long x,long long y){ if(s==x&&y==e){ return tree[h]+yan[h]*(y-x+1); } tree[h]+=(e-s+1)*yan[h]; long long mid=(s+e)/2; change(h*2,s,mid,s,mid,yan[h]); change(h*2+1,mid+1,e,mid+1,e,yan[h]); yan[h]=0; if(x>mid)return chaxun(h*2+1,mid+1,e,x,y); else if(y<=mid)return chaxun(h*2,s,mid,x,y); else return chaxun(h*2,s,mid,x,mid)+chaxun(h*2+1,mid+1,e,mid+1,y); } int main(){ long long i,j,k,m,n,x,y,z; scanf("%lld%lld",&m,&n); for(i=1;i<=m;i++){ scanf("%lld",&a[i]); } create(1,1,m); char p; for(i=1;i<=n;i++){ getchar(); scanf("%c",&p); if(p=='Q'){ scanf("%lld%lld",&x,&y); printf("%lld\n",chaxun(1,1,m,x,y)); } if(p=='C'){ scanf("%lld%lld%lld",&x,&y,&z); change(1,1,m,x,y,z); } } return 0; }