首先垃圾回收可以先把删除的树的根给放进栈里,然后要用的时候取出来并把他的左右儿子给塞回去。
其次是pushdown里面下穿懒标记时要判是否有左右儿子,不然把0给下穿了,下一次答案就不一定对了。
改玩的代码:
```cpp
#include<bits/stdc++.h>
#define ls(rt) T[rt].l
#define rs(rt) T[rt].r
#define mid (l+r>>1)
using namespace std;
const int null=2e3;
const int N=2e5+1;
mt19937 rnd(233);
int root,X,Y,Z;
int st[N],top;
int read() {
int x=0; bool f=true; char ch=0;
while (!isdigit(ch) ) f&=(ch!='-'),ch=getchar();
while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
return f?x:-x;
}
struct node
{
int l,r,size,key;
int val,col; bool rev;
int sum,pre,suf,ans;
void assign(int Col) {
col=Col,val=Col,sum=size*Col;
if (Col<0) pre=suf=0,ans=Col;
else pre=suf=ans=sum;
}
void reverse() {
rev^=1; swap(l,r);
swap(pre,suf);
}
}T[N];
int Node(int val)
{
int rt=st[top--];
if(ls(rt))
st[++top]=ls(rt);
if(rs(rt))
st[++top]=rs(rt);
ls(rt)=rs(rt)=0;
T[rt].col=null;
T[rt].rev=0;
T[rt].size=1,T[rt].key=rnd();
T[rt].val=T[rt].sum=T[rt].ans=val;
T[rt].pre=T[rt].suf=max(val,0);
T[rt].col=null; return rt;
}
void pushup(int rt)
{
T[rt].size=T[ls(rt)].size+T[rs(rt)].size+1;
T[rt].sum=T[ls(rt)].sum+T[rt].val+T[rs(rt)].sum;
T[rt].pre=max(T[ls(rt)].pre,T[ls(rt)].sum+T[rt].val+T[rs(rt)].pre);
T[rt].suf=max(T[rs(rt)].suf,T[ls(rt)].suf+T[rt].val+T[rs(rt)].sum);
T[rt].ans=max(max(T[ls(rt)].ans,T[rs(rt)].ans),T[ls(rt)].suf+T[rt].val+T[rs(rt)].pre);
}
void pushdown(int rt)
{
if (T[rt].col^null) {
int col=T[rt].col,l=ls(rt),r=rs(rt);
if(l)
T[l].assign(col);
if(r)
T[r].assign(col);
T[rt].col=null,T[rt].rev=0;
}if (T[rt].rev) {
T[rt].rev=0; int l=ls(rt),r=rs(rt);
if(l)
T[l].reverse();
if(r)
T[r].reverse();
}
}
void split(int now,int k,int &x,int &y)
{
if (!now) return x=y=0,void(); pushdown(now);
if (k<=T[ls(now)].size) y=now,split(ls(now),k,x,ls(now) );
else x=now,split(rs(now),k-T[ls(now)].size-1,rs(now),y);
pushup(now);
}
int merge(int x,int y)
{
if (!x||!y) return x^y;
pushdown(x),pushdown(y);
if (T[x].key>T[y].key) {
rs(x)=merge(rs(x),y);
pushup(x); return x;
}else {
ls(y)=merge(x,ls(y) );
pushup(y); return y;
}
}
int build(int l,int r) {
if (l==r) return Node(read() );
int L=build(l,mid),R=build(mid+1,r);
return merge(L,R);
}
void solve(int x,int y,int op)
{
split(root,x-1,X,Y),split(Y,y,Y,Z);
if (op==1) T[Y].reverse();
if (op==2) T[Y].assign(read() );
if (op==3) printf("%d\n",T[Y].sum);
if (op==4) printf("%d\n",T[Y].ans);
if (op) root=merge(merge(X,Y),Z);
else root=merge(X,Z),st[++top]=Y;
}
int main()
{
int n=read(),m=read();
for (int i=1;i<N;i++) st[++top]=i;
root=build(1,n); T[0].ans=-1e9;
while (m--)
{
int x,y; string opt; cin>>opt;
if (opt!="GET") x=read(),y=read();
if (opt=="INSERT") {
split(root,x,X,Y);
X=merge(X,build(1,y) );
root=merge(X,Y);
}if (opt=="DELETE") solve(x,y,0);
if (opt=="REVERSE") solve(x,y,1);
if (opt=="MAKE-SAME") solve(x,y,2);
if (opt=="GET-SUM") solve(x,y,3);
if (opt=="MAX-SUM") solve(x,y,4);
if (opt=="GET") solve(read(),1,3);
}
return 0;
}
```
by tangyigeng @ 2023-04-25 00:01:12
@[tangyigeng](/user/654992) thx,通过了
by OldDriverTree @ 2023-04-25 20:24:56