题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数加上x
2.求出某区间每一个数的和
思路
加lazy的线段树
#include #define maxn 1000000 #define max(x,y) x>y?x:y #define min(x,y) x'9'){if (ch=='-')p=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*p; } int k=0; int pushdown(int p,int len) { t[p<<1].lazy+=t[p].lazy; t[p<<1|1].lazy+=t[p].lazy; t[p<<1].x+=t[p].lazy*(len-len/2); t[p<<1|1].x+=t[p].lazy*(len/2); t[p].lazy=0; } int make(int p,int l,int r) { int m=(l+r)>>1; if (l==r) { k++; t[p].x=a[k]; return 0; } make(p<<1,l,m); make(p<<1|1,m+1,r); t[p].x=t[p<<1].x+t[p<<1|1].x; } int insert(int p,int l,int r,int x,int y,int k) { int m=(l+r)>>1; if (x<=l&&y>=r) { t[p].lazy+=k; t[p].x+=(r-l+1)*k; return 0; } if (t[p].lazy) pushdown(p,r-l+1); if (y<=m) insert(p<<1,l,m,x,y,k); else if (x>m) insert(p<<1|1,m+1,r,x,y,k); else { insert(p<<1,l,m,x,m,k); insert(p<<1|1,m+1,r,m+1,y,k); } t[p].x=t[p<<1].x+t[p<<1|1].x; } LL find(int p,int l,int r,int x,int y) { int m=(l+r)>>1; if (x<=l&&y>=r) return t[p].x; if (t[p].lazy) pushdown(p,r-l+1); if (y<=m) return find(p<<1,l,m,x,y); else if (x>m) return find(p<<1|1,m+1,r,x,y); else return find(p<<1,l,m,x,m)+find(p<<1|1,m+1,r,m+1,y); } int main() { int n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(); make(1,1,n); for (int i=1;i<=m;i++) { int z=read(),x=read(),y=read(); if (z==1) { int xx=read(); insert(1,1,n,x,y,xx); } else printf("%lld\n",find(1,1,n,x,y)); } }
Comments NOTHING