Lvat_s Blog

恶心的线段树

维护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;
}