把操作改成形如 ( a,b ) 表示加上 a 之后对 b 取 max 的意思。
每个点维护当前的 a , b ，还有历史最大的 a , b 即 ma , mb 。
因为最后的答案是 tp[ x ] + ma , mb 中的一个，所以这样维护。之所以不直接维护 max{ tp[ x ]+ma , mb } ，是为了方便转移。
转移 a , b 的时候就是 \( max{max{x+a,b}+a',b'} <=> max{x+a+a',max{b+a',b'}} \) 。
转移 ma , mb 的时候，理解一下，就是 \( ma=max{ma,a+ma'} , mb=max{mb,max{mb',b+ma'}} \)
好像可以这样理解？https://blog.csdn.net/qq_39972971/article/details/79147791
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
ll Mx(ll a,ll b){return a>b?a:b;}
ll Mn(ll a,ll b){return a<b?a:b;}
const int N=5e5+,M=N<<; const ll INF=5e14+;
void upd(ll &x){x=Mx(x,-INF);x=Mn(x,INF);return;} int n,m,tp[N],tot,Ls[M],Rs[M];
ll a[M],b[M],ma[M],mb[M];
void build(int l,int r,int cr)
{
b[cr]=mb[cr]=-INF;
if(l==r){b[cr]=mb[cr]=tp[l];return;}
int mid=l+r>>;
ls=++tot; build(l,mid,ls);
rs=++tot; build(mid+,r,rs);
}
void cz(int u,int v)
{
mb[v]=Mx(mb[v],Mx(b[v]+ma[u],mb[u]));//b[v]+ma[u] not mb[v]+ma[u]
ma[v]=Mx(ma[v],a[v]+ma[u]);//a[v]+ma[u] not ma[v]+ma[u]
b[v]=Mx(b[v]+a[u],b[u]);
a[v]=Mx(a[v]+a[u],-INF);//only here
}
void pshd(int cr)
{
if(ls)cz(cr,ls); if(rs)cz(cr,rs);
a[cr]=ma[cr]=; b[cr]=mb[cr]=-INF;
}
void mdfy(int l,int r,int cr,int L,int R)
{
if(l>=L&&r<=R){cz(,cr); return;}
int mid=l+r>>; pshd(cr);
if(L<=mid)mdfy(l,mid,ls,L,R);
if(mid<R)mdfy(mid+,r,rs,L,R);
}
int qry(int l,int r,int cr,int p)
{
if(l==r)return cr;int mid=l+r>>;
pshd(cr);
if(p<=mid)return qry(l,mid,ls,p);
else return qry(mid+,r,rs,p);
}
int main()
{
n=rdn();m=rdn();
for(int i=;i<=n;i++)tp[i]=rdn();
tot=;build(,n,);
for(int i=,op,l,r,x;i<=m;i++)
{
op=rdn();
if(op<=)
{
l=rdn();r=rdn();x=rdn();
if(op==)a[]=ma[]=x,b[]=mb[]=-INF;
if(op==)a[]=ma[]=-x,b[]=mb[]=;
if(op==)a[]=ma[]=-INF,b[]=mb[]=x;
mdfy(,n,,l,r);
}
else
{
x=rdn(); int cr=qry(,n,,x);
if(op==)printf("%lld\n",Mx(tp[x]+a[cr],b[cr]));
if(op==)printf("%lld\n",Mx(tp[x]+ma[cr],mb[cr]));
}
}
return ;
}