题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和
输出格式:
输出包含若干行整数,即为所有操作2的结果。
输入输出样例
输入样例#1:
5 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4
输出样例#1:
11 8 20
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=1000,M<=10000
对于100%的数据:N<=100000,M<=100000
(数据已经过加强^_^,保证在int64/long long数据范围内)
#include<cstdio> #define N 110000 long long A[N],sum[N*4],a[N*4]; int n,m; void add(int k1,int l,int r,int x){ sum[k1]+=x*(r-l+1); a[k1]+=x; } void change(int k1){ sum[k1]=sum[k1*2]+sum[k1*2+1]; } void buildtree(int k1,int l,int r){ if(l==r){ sum[k1]=A[l]; return; } int mid=(l+r)>>1; buildtree(k1*2,l,mid); buildtree(k1*2+1,mid+1,r); change(k1); } void pushdown(int k1,int l,int r){ int mid=(r+l)>>1; add(k1*2,l,mid,a[k1]); add(k1*2+1,mid+1,r,a[k1]); a[k1]=0; } void addall(int k1,int l,int r,int L,int R,int x){ if(l>R||r<L) return; if(L<=l&&R>=r){ add(k1,l,r,x) ; return; } int mid=(l+r)>>1; if(a[k1]!=0) pushdown(k1,l,r); addall(k1*2,l,mid,L,R,x); addall(k1*2+1,mid+1,r,L,R,x); change(k1); } long long find(int k1,int l,int r,int L,int R){ if(l>R||r<L) return 0; if(L<=l&&R>=r) return sum[k1]; int mid=(l+r)>>1; if(a[k1]!=0) pushdown(k1,l,r); return find(k1*2,l,mid,L,R)+find(k1*2+1,mid+1,r,L,R); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&A[i]); buildtree(1,1,n); for(int i=1;i<=m;++i){ int k,l1,r1,x; scanf("%d%d%d",&k,&l1,&r1); if(k==1){ scanf("%d",&x); addall(1,1,n,l1,r1,x); } else printf("%lld ",find(1,1,n,l1,r1)); } return 0; } //https://www.luogu.org/problem/show?pid=3372#sub