把操作改成形如 ( 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=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',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+5,M=N<<1; const ll INF=5e14+5; 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>>1; ls=++tot; build(l,mid,ls); rs=++tot; build(mid+1,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]=0; b[cr]=mb[cr]=-INF; } void mdfy(int l,int r,int cr,int L,int R) { if(l>=L&&r<=R){cz(0,cr); return;} int mid=l+r>>1; pshd(cr); if(L<=mid)mdfy(l,mid,ls,L,R); if(mid<R)mdfy(mid+1,r,rs,L,R); } int qry(int l,int r,int cr,int p) { if(l==r)return cr;int mid=l+r>>1; pshd(cr); if(p<=mid)return qry(l,mid,ls,p); else return qry(mid+1,r,rs,p); } int main() { n=rdn();m=rdn(); for(int i=1;i<=n;i++)tp[i]=rdn(); tot=1;build(1,n,1); for(int i=1,op,l,r,x;i<=m;i++) { op=rdn(); if(op<=3) { l=rdn();r=rdn();x=rdn(); if(op==1)a[0]=ma[0]=x,b[0]=mb[0]=-INF; if(op==2)a[0]=ma[0]=-x,b[0]=mb[0]=0; if(op==3)a[0]=ma[0]=-INF,b[0]=mb[0]=x; mdfy(1,n,1,l,r); } else { x=rdn(); int cr=qry(1,n,1,x); if(op==4)printf("%lld ",Mx(tp[x]+a[cr],b[cr])); if(op==5)printf("%lld ",Mx(tp[x]+ma[cr],mb[cr])); } } return 0; }