描述
给定长度为N（N<=105）的数列A，然后输入M行操作指令。
第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。
第二类指令形如“M l r d”，表示把数列中第l~r个数都乘d。
第三类指令形如“Q l r”，表示询问数列中第l~r个数的和。
对于每个询问，输出一个整数表示答案。
输入
第一行包含两个整数N和M。
第二行包含N个整数A[i]。
接下来M行表示M条指令，每条指令的格式如题目描述所示。
数据范围：1≤N，M≤105，|d|≤104，|A[i]|≤109，数据保证操作指令过程中所有数的和小于263-1。
输出
对于每个询问，输出一个整数表示答案。
每个答案占一行。
样例输入
10 5
1 2 3 4 5 6 7 8 9 10
Q 1 4
C 1 6 3
Q 1 5
M 1 5 3
Q 1 5
样例输出
10
30
90
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10,inf = 0x3f3f3f3f; int n,m; int c[N]; ll t[N * 4],add[N * 4],mul[N * 4]; //分别是线段树、加法、乘法 void build(int k,int l,int r) { add[k] = 0; mul[k] = 1; //建树顺便初始化 if(l == r) { t[k] = c[l]; return; } int mid = (l + r) / 2; build(k * 2,l,mid); build(k * 2 + 1,mid + 1,r); t[k] = t[k * 2] + t[k * 2 + 1]; } void pushdown(int k,int l,int r,int mid) { //更新顺序：树、乘、加 //左子树 = 左子树 * k层的积 + [l-mid]区间和 右子树 = 右子树 * k层的积 + [mid-r]区间和 t[k * 2] = t[k * 2] * mul[k] + (mid - l + 1) * add[k]; t[k * 2 + 1] = t[k * 2 + 1] * mul[k] + (r - mid) * add[k]; //乘法 = 左/右儿子 * 父节点mul mul[k * 2] = mul[k * 2] * mul[k]; mul[k* 2 + 1] = mul[k * 2 + 1] * mul[k]; //加法 = 左右儿子 * 父节点mul + 父节点add add[k * 2] = add[k * 2] * mul[k] + add[k]; add[k * 2 + 1] = add[k * 2 + 1] * mul[k] + add[k]; mul[k] = 1; add[k] = 0; //重置父节点 } void multiply(int k,int l,int r,int a,int b,int w) { if(l > b || r < a)return; if(l >= a && r <= b) { //乘法 ： 树、乘、加都要乘w mul[k] *= w; add[k] *= w; t[k] *= w; return; } int mid = (l + r) / 2; pushdown(k,l,r,mid); multiply(k * 2,l,mid,a,b,w); multiply(k * 2 + 1,mid + 1,r,a,b,w); t[k] = t[k * 2] + t[k * 2 + 1]; } void modify(int k,int l,int r,int a,int b,int w) { if(l > b || r < a)return; if(l >= a && r <= b) { t[k] += w * (r - l + 1); //k层 的[l-r]区间和都加上w add[k] += w; return; } int mid = (l + r) / 2; pushdown(k,l,r,mid); modify(k * 2,l,mid,a,b,w); modify(k * 2 + 1,mid + 1,r,a,b,w); t[k] = t[k * 2] + t[k * 2 + 1]; } ll query(int k,int l,int r,int a,int b) { if(l > b || r < a)return 0; if(l >= a && r <= b)return t[k]; int mid = (l + r) / 2; pushdown(k,l,r,mid); ll res = 0; res += query(k * 2,l,mid,a,b); res += query(k * 2 + 1,mid + 1,r,a,b); return res; } int main() { cin >> n >> m; for(int i = 1;i <= n;i++)scanf("%d",&c[i]); build(1,1,n); int x,y,z; char op; while(m--) { getchar(); scanf("%c",&op); if(op == 'M') { scanf("%d %d %d",&x,&y,&z); multiply(1,1,n,x,y,z);//x~y乘z } else if(op == 'C') { scanf("%d %d %d",&x,&y,&z); modify(1,1,n,x,y,z);//x~y加z } else { scanf("%d %d",&x,&y); printf("%lld\n",query(1,1,n,x,y)); //查询x~y区间和 } } return 0; }