这是个远古巨坑阿qwq
没有历史最大值还是能比较好做的.可能会有一个想法,就是直接维护线段树每个结点出现过的历史最大值,每次最大值变化就更新.但是有个问题:可能一个点能影响历史最大值的标记还没被及时下放,就被父亲标记覆盖了,这样就可能得到错误答案
考虑新定义标记\((a,b)\),表示对一个结点先加\(a\)然后和\(b\)求max.这种定义下,区间加就是\((x,-\infty)\),赋值就是\((-\infty,x)\).然后如果两个标记合并,假设是\((a,b)\)并上\((x,y)\),那么应该是\((a+x,max(b+x,y))\).手玩发现这样是对的
但是还是没解决历史最大值的问题.现在多开一种标记,表示影响历史最大值的标记.这一种标记\((a,b)\)并上\((x,y)\)应该是\((max(a,x),max(b,y))\),原因是可以看成是两个分段函数取max
然后就没然后了,线段树怎么搞就怎么搞
#include<bits/stdc++.h>
#define LL long long
#define ldb long double
#define il inline
#define re register
using namespace std;
const int N=1e5+10,inf=999999999;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
struct TAG
{
int a,b;
TAG(){a=0,b=-inf;}
TAG(int na,int nb){a=na,b=nb;}
il void clr(){a=0,b=-inf;}
TAG operator + (const TAG &bb) const {return TAG(max(-inf,a+bb.a),max(b+bb.a,bb.b));} //小心boom int
TAG operator & (const TAG &bb) const {return TAG(max(a,bb.a),max(b,bb.b));}
}nt[N<<2],ht[N<<2];
int ns[N<<2],hs[N<<2];
il void psup(int o){hs[o]=max(hs[o<<1],hs[o<<1|1]),ns[o]=max(ns[o<<1],ns[o<<1|1]);}
il void ad(int o,TAG x,TAG y)
{
ht[o]=ht[o]&(nt[o]+y);
nt[o]=nt[o]+x;
hs[o]=max(hs[o],max(ns[o]+y.a,y.b));
ns[o]=max(ns[o]+x.a,x.b);
}
il void psdn(int o)
{
ad(o<<1,nt[o],ht[o]),ad(o<<1|1,nt[o],ht[o]);
nt[o].clr(),ht[o].clr();
}
#define mid ((l+r)>>1)
void modif(int o,int l,int r,int ll,int rr,TAG x)
{
if(ll<=l&&r<=rr) {ad(o,x,x);return;}
psdn(o);
if(ll<=mid) modif(o<<1,l,mid,ll,rr,x);
if(rr>mid) modif(o<<1|1,mid+1,r,ll,rr,x);
psup(o);
}
int quer(int o,int l,int r,int ll,int rr,bool op)
{
if(ll<=l&&r<=rr) return op?hs[o]:ns[o];
psdn(o);
int an=-inf;
if(ll<=mid) an=max(an,quer(o<<1,l,mid,ll,rr,op));
if(rr>mid) an=max(an,quer(o<<1|1,mid+1,r,ll,rr,op));
psup(o);
return an;
}
void bui(int o,int l,int r)
{
if(l==r){ns[o]=hs[o]=rd();return;}
bui(o<<1,l,mid),bui(o<<1|1,mid+1,r);
psup(o);
}
int n,q;
int main()
{
n=rd();
bui(1,1,n);
q=rd();
char cc[2];
while(q--)
{
scanf("%s",cc);
if(cc[0]=='Q')
{
int l=rd(),r=rd();
printf("%d\n",quer(1,1,n,l,r,0));
}
else if(cc[0]=='A')
{
int l=rd(),r=rd();
printf("%d\n",quer(1,1,n,l,r,1));
}
else if(cc[0]=='P')
{
int l=rd(),r=rd(),x=rd();
modif(1,1,n,l,r,TAG(x,-inf));
}
else
{
int l=rd(),r=rd(),x=rd();
modif(1,1,n,l,r,TAG(-inf,x));
}
}
return 0;
}