恶心的线段树
维护6个标记
最后调不出来找来标程
原来标记的先后顺序也有关系
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N=100005,INF=2100000000;
int T,E,a[N];
struct SegTree{
int add,mx,cov,l,r;
}tree[4*N],histree[4*N];
void CheckMax(int rt,int val){histree[rt].mx=max(histree[rt].mx,val);}
void HisAdd(int rt,int val){
CheckMax(rt,tree[rt].mx+val);
if(tree[rt].cov>-INF)histree[rt].cov=max(histree[rt].cov,tree[rt].cov+val);
else histree[rt].add=max(histree[rt].add,tree[rt].add+val);
}
void HisCover(int rt,int val){
CheckMax(rt,val);
histree[rt].cov=max(histree[rt].cov,val);
}
void Add(int rt,int val){
CheckMax(rt,tree[rt].mx+=val);
if(tree[rt].cov>-INF)histree[rt].cov=max(histree[rt].cov,tree[rt].cov+=val);
else histree[rt].add=max(histree[rt].add,tree[rt].add+=val);
}
void Cover(int rt,int val){
CheckMax(rt,tree[rt].mx=val);
histree[rt].cov=max(histree[rt].cov,tree[rt].cov=val);
tree[rt].add=0;
}
void Pushdown(int rt){
if(histree[rt].add){
HisAdd(rt<<1,histree[rt].add);
HisAdd(rt<<1|1,histree[rt].add);
histree[rt].add=0;
}
if(histree[rt].cov!=-INF){
HisCover(rt<<1,histree[rt].cov);
HisCover(rt<<1|1,histree[rt].cov);
histree[rt].cov=-INF;
}
if(tree[rt].add){
Add(rt<<1,tree[rt].add);
Add(rt<<1|1,tree[rt].add);
tree[rt].add=0;
}
if(tree[rt].cov!=-INF){
Cover(rt<<1,tree[rt].cov);
Cover(rt<<1|1,tree[rt].cov);
tree[rt].cov=-INF;
}
}
void Pushup(int rt){
histree[rt].mx=max(histree[rt].mx,max(histree[rt<<1].mx,histree[rt<<1|1].mx));
tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx);
}
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].add=0;
tree[rt].mx=-INF;
tree[rt].cov=-INF;
histree[rt].l=l;
histree[rt].r=r;
histree[rt].add=0;
histree[rt].mx=-INF;
histree[rt].cov=-INF;
if(l==r){tree[rt].mx=histree[rt].mx=a[l];return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
void Plus(int rt,int l,int r,int val){
if(l<=tree[rt].l && tree[rt].r<=r){
Add(rt,val);
return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Plus(rt<<1,l,r,val);
if(r>mid)Plus(rt<<1|1,l,r,val);
Pushup(rt);
}
void Change(int rt,int l,int r,int val){
if(l<=tree[rt].l && tree[rt].r<=r){
Cover(rt,val);
return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Change(rt<<1,l,r,val);
if(r>mid)Change(rt<<1|1,l,r,val);
Pushup(rt);
}
int Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].mx;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1,ans=-INF;
if(l<=mid)ans=max(ans,Query(rt<<1,l,r));
if(r>mid)ans=max(ans,Query(rt<<1|1,l,r));
return ans;
}
int Ask(int rt,int l,int r){
if(l<=histree[rt].l && histree[rt].r<=r)return histree[rt].mx;
Pushdown(rt);
int mid=histree[rt].l+histree[rt].r>>1,ans=-INF;
if(l<=mid)ans=max(ans,Ask(rt<<1,l,r));
if(r>mid)ans=max(ans,Ask(rt<<1|1,l,r));
return ans;
}
int main(){
freopen("3064.in","r",stdin);
freopen("3064.out","w",stdout);
scanf("%d",&T);
for(int i=1;i<=T;i++)scanf("%d",&a[i]);
Build(1,1,T);
scanf("%d",&E);
for(int i=1;i<=E;i++){
char s[10];
int x,y,z;
scanf("%s",s);
if(s[0]=='Q'){scanf("%d %d",&x,&y);printf("%d\n",Query(1,x,y));}
if(s[0]=='A'){scanf("%d %d",&x,&y);printf("%d\n",Ask(1,x,y));}
if(s[0]=='P'){scanf("%d %d %d",&x,&y,&z);Plus(1,x,y,z);}
if(s[0]=='C'){scanf("%d %d %d",&x,&y,&z);Change(1,x,y,z);}
}
return 0;
}
