题目描述 Description
给你N个数,有两种操作:
1:给区间[a,b]的所有数增加X 2:询问区间[a,b]的数的和。 输入描述 Input Description
第一行一个正整数n,接下来n行n个整数,
再接下来一个正整数Q,每行表示操作的个数,
如果第一个数是1,后接3个正整数,
表示在区间[a,b]内每个数增加X,如果是2,
表示操作2询问区间[a,b]的和是多少。
pascal选手请不要使用readln读入
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 2 3
样例输出 Sample Output
9
数据范围及提示 Data Size & Hint
数据范围
1<=n<=200000
1<=q<=200000
#includeint A[200005];struct tree{long long sum,add;int l,r;}t[800005];void push_up(int u){t[u].sum=t[u<<1].sum+t[u<<1|1].sum;}void push_down(int u){t[u<<1].add+=t[u].add;t[u<<1|1].add+=t[u].add;t[u<<1].sum+=(t[u<<1].r-t[u<<1].l+1)*t[u].add;t[u<<1|1].sum+=(t[u<<1|1].r-t[u<<1|1].l+1)*t[u].add;t[u].add=0;}void build(int u,int l,int r){t[u].l=l;t[u].r=r;if(l==r){t[u].sum=A[l];return ;}int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);push_up(u);}void update(int u,int l,int r,int a){if(t[u].l==l&&t[u].r==r){t[u].add+=a;t[u].sum+=a*(t[u].r-t[u].l+1);return;}if(t[u].add) push_down(u);int mid=(t[u].l+t[u].r)>>1;if(r<=mid) update(u<<1,l,r,a);else if(l>mid) update(u<<1|1,l,r,a);else {update(u<<1,l,mid,a);update(u<<1|1,mid+1,r,a);}push_up(u);}long long query(int u,int l,int r){if(t[u].l>=l&&t[u].r<=r) return t[u].sum;if(t[u].add) push_down(u);long long ans=0,mid=(t[u].l+t[u].r)>>1;if(r<=mid) ans+=query(u<<1,l,r);else if(l>mid) ans+=query(u<<1|1,l,r);else{ans+=query(u<<1,l,mid);ans+=query(u<<1|1,mid+1,r);}return ans;}int main(){int n,q;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&A[i]);build(1,1,n);scanf("%d",&q);for(int i=1;i<=q;i++) {int cmd;scanf("%d",&cmd);if(cmd==1){int L,R,X;scanf("%d%d%d",&L,&R,&X);update(1,L,R,X);}else{int L,R;scanf("%d%d",&L,&R);printf("%lld\n",query(1,L,R));}}return 0;}