给出N(1 ≤ N ≤ 50,000)个数的序列A，下标从1到N，每个元素值均不超过INT_MAX。有两种操作：
(1) Q i j：询问区间[i, j]之间的最大值与最小值的差值
(2) C i j：将A[i]增加j，j是一个整数。如果多次对同一个元素进行C操作，导致溢出，保留自然溢出后的结果。
一共有M (1 ≤ M ≤ 200,000) 次操作，对每个Q操作，输出一行，回答提问。
第1行：2个整数N, M
第2行：N个元素
接下来M行，每行一个操作
对每个Q操作，在一行上输出答案
Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)
5 4 1 2 3 4 5 Q 2 4 C 1 2 C 2 1 Q 1 3此题可以用普通线段树做，但是今天新学了zkw线段树（请百度），然后就尝试用最普通的版本来做这道题，没有用差分思想（虽然同学们理解了但是我并不是很明白，所以等理解了再来补上）
zkw线段树将所有节点严格放在最下面的同一层叶子节点上，所以会有天然的数学关系来从下向上更新。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long LL; const int Max=50000; int N,T,M,X; int Trx[4*Max+5],Trn[4*Max+5]; void build(){ for(X=1; X<=N; X<<=1); --X; int MM=Max*4; for(int i=0; i<=MM; ++i) Trn[i]=0x3f3f3f,Trx[i]=-0x3f3f3f; for(int i=X+1; i<=X+N; ++i) scanf("%d",&Trx[i]),Trn[i]=Trx[i]; for(int i=X; i; --i){ Trx[i]=max(Trx[i<<1],Trx[i<<1|1]); Trn[i]=min(Trn[i<<1],Trn[i<<1|1]); } } void add(int p,int val){ p+=X; Trx[p]+=val,Trn[p]+=val; for(p>>=1; p; p>>=1){ Trx[p]=max(Trx[p<<1],Trx[p<<1|1]); Trn[p]=min(Trn[p<<1],Trn[p<<1|1]); } } int cnt(int s,int t){ int ansx=-0x3f3f3f,ansn=0x3f3f3f; s+=X,t+=X; if(s==t)return Trx[s]-Trn[s]; else ansx=max(Trx[s],Trx[t]),ansn=min(Trn[s],Trn[t]); for(; s^t^1; s>>=1,t>>=1){ if(~s&1){ ansx=max(ansx,Trx[s^1]); ansn=min(ansn,Trn[s^1]); } if(t&1){ ansx=max(ansx,Trx[t^1]); ansn=min(ansn,Trn[t^1]); } } //printf("max=%d min=%d\n",ansx,ansn); return ansx-ansn; } int main(){ scanf("%d%d",&N,&M); build(); char ord[3]; int a,b; for(int i=1; i<=M; ++i){ scanf("%s",ord); if(ord[0]=='C'){ scanf("%d%d",&a,&b); add(a,b); } else { scanf("%d%d",&a,&b); printf("%d\n",cnt(min(a,b),max(a,b))); } } return 0; }
