如题,在初步调试过后猜测是 push_down 或者push_np(resize) 的问题
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10,UDF=-0x3f3f3f3f;
int n,q,a[N];
struct node{
int val,S,rk,ls,rs,size,tagrev,tagdif,sx,lx,rx;
};
struct treap{
node tr[N];
int tot=1,root=1;
int newnode(int val){tr[++tot]={val,0,rand(),0,0,1,0,UDF,UDF,UDF,UDF};return tot;}
void resize(int u)
{
auto a=tr[tr[u].ls],b=tr[tr[u].rs];
tr[u].S=a.S+b.S+tr[u].val;
tr[u].size=a.size+b.size+1;
tr[u].tagdif=UDF,tr[u].tagrev=0;
tr[u].lx=max({0,a.lx,a.S+tr[u].val,a.S+tr[u].val+b.lx});
tr[u].rx=max({0,b.rx,b.S+tr[u].val,b.S+tr[u].val+a.rx});
tr[u].sx=max({0,a.sx,b.sx,tr[u].val,tr[u].val+a.rx,tr[u].val+b.lx,tr[u].val+a.rx+b.lx});
}
void push_down(int u)
{
if (tr[u].tagrev)
{
tr[tr[u].ls].tagrev^=1,tr[tr[u].rs].tagrev^=1;
swap(tr[u].ls,tr[u].rs);
resize(u);
tr[u].tagrev=0;
}
if (tr[u].tagdif!=UDF)
{
tr[tr[u].ls].tagdif=tr[tr[u].rs].tagdif=tr[u].tagdif;
tr[u].S=tr[u].size*tr[u].tagdif;
if (tr[u].tagdif>0) tr[u].sx=tr[u].lx=tr[u].rx=tr[u].S;
else tr[u].sx=tr[u].lx=tr[u].rx=tr[u].S;
resize(u);
tr[u].tagdif=UDF;
}
}
void split(int now,int rk,int &l,int &r)
{
if (!now){l=r=0;return;}
push_down(now);
int siz=tr[tr[now].ls].size;
if (rk<=siz) r=now,split(tr[now].ls,rk,l,tr[now].ls);
else l=now,split(tr[now].rs,rk-siz-1,tr[now].rs,r);
resize(now);
}
int merge(int u,int v)
{
if (!u || !v) return u+v;
if (tr[u].rk<tr[v].rk)
{
push_down(u);
tr[u].rs=merge(tr[u].rs,v);
resize(u);
return u;
}
else
{
push_down(v);
tr[v].ls=merge(u,tr[v].ls);
resize(v);
return v;
}
}
int ins[N];
void insert(int pos,int tot)
{
int l,r;
split(root,pos,l,r);
for (int i=1;i<=tot;i++) l=merge(l,newnode(ins[i]));
root=merge(l,r);
}
void del(int pos,int tot)
{
int L=pos+1,R=pos+tot;
int l,mid,r;
split(root,R,l,r);
split(l,L-1,l,mid);
root=merge(l,r);
}
void modify(int pos,int tot,int x)
{
int L=pos+1,R=pos+tot;
int l,mid,r;
split(root,R,l,r);
split(l,L-1,l,mid);
tr[mid].tagdif=x;
root=merge(merge(l,mid),r);
}
void reverse(int pos,int tot)
{
int L=pos+1,R=pos+tot;
int l,mid,r;
split(root,R,l,r);
split(l,L-1,l,mid);
tr[mid].tagrev^=1;
root=merge(merge(l,mid),r);
}
int queryS(int pos,int tot)
{
int L=pos+1,R=pos+tot;
int l,mid,r;
split(root,R,l,r);
split(l,L-1,l,mid);
int ans=tr[mid].S;
root=merge(merge(l,mid),r);
return ans;
}
int queryQ(){return tr[root].sx;}
};
int main()
{
srand(time(0));
scanf("%d %d",&n,&q);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
treap tre;
for (int i=1;i<=n;i++) tre.root=tre.merge(tre.root,tre.newnode(a[i]));
for (int opt=1;opt<=q;opt++)
{
char op[10];int pos,tot,x;
scanf("%s",op);
if (op[0]=='I')
{
scanf("%d %d",&pos,&tot);
for (int i=1;i<=tot;i++) scanf("%d",&tre.ins[i]);
tre.insert(pos,tot);
}
else if (op[0]=='D')
{
scanf("%d %d",&pos,&tot);
tre.del(pos,tot);
}
else if (op[2]=='K')
{
scanf("%d %d %d",&pos,&tot,&x);
tre.modify(pos,tot,x);
}
else if (op[0]=='R')
{
scanf("%d %d",&pos,&tot);
tre.reverse(pos,tot);
}
else if (op[0]=='G')
{
scanf("%d %d",&pos,&tot);
printf("%d\n",tre.queryS(pos,tot));
}
else if (op[2]=='X') printf("%d\n",tre.queryQ());
}
return 0;
}