题目描述
如题，已知一个数列，你需要进行下面两种操作：
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的结果。
输入输出样例
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n,m,i,j,p,op,k; long long a[100002]; struct node { int l; int r; long long lazy; long long sum; }t[400008]; void qiuhe(int p) { t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum; return; } void faqian(int p) { if(t[p].l == t[p].r || t[p].lazy == 0) return; t[p * 2].lazy += t[p].lazy; t[p * 2].sum += t[p].lazy * (t[p * 2].r - t[p * 2].l + 1); t[p * 2 + 1].lazy += t[p].lazy; t[p * 2 + 1].sum += t[p].lazy * (t[p * 2 + 1].r - t[p * 2 + 1].l + 1); t[p].lazy = 0; } void buildtree(int p,int l,int r) { t[p].l = l; t[p].r = r; t[p].lazy = 0; if(l == r) { t[p].sum = a[l]; return; } int mid = (l + r) / 2; buildtree(p * 2,l,mid); buildtree(p * 2 + 1,mid+1,r); qiuhe(p); } void add(int p,int l,int r,int w) { faqian(p); if(l == t[p].l && r == t[p].r) { t[p].sum += (r - l + 1) * w; t[p].lazy = w; return; } int mid = (t[p].l + t[p].r) / 2; if(mid >= r) add(p * 2,l,r,w); else if(mid < l) add(p * 2 + 1,l,r,w); else { add(p * 2,l,mid,w); add(p * 2 + 1,mid+1,r,w); } qiuhe(p); } long long xunwen(int p,int l,int r) { faqian(p); if(l == t[p].l && r == t[p].r) return t[p].sum; int mid = (t[p].l + t[p].r) / 2; if(mid >= r) return xunwen(p * 2,l,r); if(mid < l) return xunwen(p * 2 + 1,l,r); return xunwen(p * 2,l,mid) + xunwen(p * 2 + 1,mid+1,r); } int main() { int l,r; long long k; scanf("%d %d",&n,&m); for(i = 1;i <= n;i++) { scanf("%lld",&a[i]); } buildtree(1,1,n); for(i = 1;i <= m;i++) { scanf("%d",&op); if(op == 1) { scanf("%d %d %d",&l,&r,&k); add(1,l,r,k); } else { scanf("%d %d",&l,&r); printf("%lld ",xunwen(1,l,r)); } } return 0; }