#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
using namespace std;
const int N=50010;
int T,M,n,s,t,num,Max[N<<3],Min[N<<3];
char op[3];
void build(){
for(int i=M+1;i<=M+n;i++)
scanf("%d",&Max[i]),Min[i]=Max[i];
for(int i=M;i>0;i--){
Max[i]=max(Max[i<<1],Max[i<<1|1]);
Max[i<<1]-=Max[i],Max[i<<1|1]-=Max[i];
Min[i]=min(Min[i<<1],Min[i<<1|1]);
Min[i<<1]-=Min[i],Min[i<<1|1]-=Min[i];
}
}
void update(int pos,int val){
int a;
Max[pos+M]+=val,Min[pos+M]+=val;
for(pos=pos+M;pos;pos>>=1){
a=max(Max[pos<<1],Max[pos<<1|1]);
Max[pos<<1]-=a,Max[pos<<1|1]-=a,Max[pos]+=a;
a=min(Min[pos<<1],Min[pos<<1|1]);
Min[pos<<1]-=a,Min[pos<<1|1]-=a,Min[pos]+=a;
}
}
void update(int s,int t,int val){
int a;
if(s==t){
update(s,val);return ;
}
Max[s+M]+=val,Min[s+M]+=val;
Max[t+M]+=val,Min[t+M]+=val;
for(s=s+M,t=t+M;s^t^1;s>>=1,t>>=1){
if(~s&1) Max[s^1]+=val,Min[s^1]+=val;
if(t&1) Max[t^1]+=val,Min[t^1]+=val;
a=max(Max[s<<1],Max[s<<1|1]);
Max[s<<1]-=a,Max[s<<1|1]-=a,Max[s]+=a;
a=min(Min[s<<1],Min[s<<1|1]);
Min[s<<1]-=a,Min[s<<1|1]-=a,Min[s]+=a;
a=max(Max[t<<1],Max[t<<1|1]);
Max[t<<1]-=a,Max[t<<1|1]-=a,Max[t]+=a;
a=min(Min[t<<1],Min[t<<1|1]);
Min[t<<1]-=a,Min[t<<1|1]-=a,Min[t]+=a;
}
a=max(Max[t<<1],Max[t<<1|1]);
Max[t<<1]-=a,Max[t<<1|1]-=a,Max[t]+=a;
a=min(Min[t<<1],Min[t<<1|1]);
Min[t<<1]-=a,Min[t<<1|1]-=a,Min[t]+=a;
while(s){
a=max(Max[s<<1],Max[s<<1|1]);
Max[s<<1]-=a,Max[s<<1|1]-=a,Max[s]+=a;
a=min(Min[s<<1],Min[s<<1|1]);
Min[s<<1]-=a,Min[s<<1|1]-=a,Min[s]+=a;
s>>=1;
}
}
int getmax(int s,int t){
int L=0,R=0,res=0;
if(s==t){
while(s) res+=Max[s],s>>=1;
return res;
}
for(s=s+M,t=t+M;s^t^1;s>>=1,t>>=1){
L+=Max[s],R+=Max[t];
if(~s&1) L=max(L,Max[s^1]);
if(t&1) R=max(R,Max[t^1]);
}
res=max(L+Max[s],R+Max[t]);
while(s) res+=Max[s>>=1];
return res;
}
int getmin(int s,int t){
int L=0,R=0,res=0;
if(s==t){
while(s) res+=Max[s],s>>=1;
return res;
}
for(s=s+M,t=t+M;s^t^1;s>>=1,t>>=1){
L+=Min[s],R+=Min[t];
if(~s&1) L=min(L,Min[s^1]);
if(t&1) R=min(R,Min[t^1]);
}
res=min(L+Min[s],R+Min[t]);
while(s) res+=Min[s>>=1];
return res;
}
int main(){
scanf("%d %d",&n,&T);
for(M=1;M<n;M<<=1);
M--,build();
while(T--){
scanf("%s%d%d",op,&s,&t);
if(op[0]=='Q') printf("%d\n",getmax(s,t)-getmin(s,t));
else scanf("%d",&num),update(s,t,num);
}
}
转载请注明原文地址: https://ju.6miu.com/read-26544.html
