如题,只在find函数下传懒标记炸了,但像lct一样在splay里也下传就没有问题,请教是怎么回事。
代码
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
int s=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=0; c=getchar();}
while(c>='0'&&c<='9'){s=s*10+c-48; c=getchar();}
x=f? s:-s;
}
const int N=5e6+10,inf=1e4;
string act[]={
"INSERT", "DELETE", "MAKE-SAME",
"REVERSE", "GET-SUM", "MAX-SUM"
};
struct splay{
int c[2],f;
int trev,tad;
int s,v,ct,lmx,rmx,mx;
} t[N]; int rot,id;
#define cl t[x].c[0]
#define cr t[x].c[1]
inline void turn(int x){
if(!x) return;
swap(cl,cr); t[x].trev^=1;
swap(t[x].lmx,t[x].rmx);
}
inline void add(int x,int val){
if(!x) return;
t[x].s=t[x].ct*val;
t[x].v=t[x].tad=val;
t[x].mx=val>0? t[x].ct*val:val;
t[x].lmx=t[x].rmx=val>0? t[x].ct*val:0;
}
inline void pd(int x){
if(t[x].trev){
t[x].trev=0;
turn(cl);
turn(cr);
}
if(t[x].tad<inf){
add(cl,t[x].tad);
add(cr,t[x].tad);
t[x].tad=inf;
}
}
inline void pu(int x){
t[x].ct=t[cl].ct+t[cr].ct+1;
t[x].s=t[cl].s+t[cr].s+t[x].v;
t[x].mx=max({ t[cl].mx, t[cr].mx, t[cl].rmx+t[x].v+t[cr].lmx});
t[x].lmx=max( t[cl].lmx, t[cl].s+t[x].v+t[cr].lmx );
t[x].rmx=max( t[cr].rmx, t[cr].s+t[x].v+t[cl].rmx );
}
inline bool get(int x){
return t[t[x].f].c[1]==x;
}
#undef cl
#undef cr
inline void rotate(int x){
int y=t[x].f, z=t[y].f, k=get(x);
t[y].c[k]=t[x].c[k^1];
if(t[y].c[k]) t[t[y].c[k]].f=y;
t[x].c[k^1]=y; if(z) t[z].c[get(y)]=x;
t[y].f=x; t[x].f=z; pu(y); pu(x);
}
int sta[N],top;
inline void splay(int x,int goal=0){
int _p=x; top=0;
while(_p) sta[++top]=_p,_p=t[_p].f;
while(top) pd(sta[top--]);
while(t[x].f!=goal){
int y=t[x].f;
if(t[y].f!=goal) rotate(get(x)==get(y)?y:x);
rotate(x);
}
if(goal==0) rot=x;
}
inline int find(int rk,int u=rot){
while(t[t[u].c[0]].ct+1!=rk){
pd(u);
if(t[t[u].c[0]].ct>=rk) u=t[u].c[0];
else rk-=t[t[u].c[0]].ct+1, u=t[u].c[1];
}
return u;
}
inline int split(int sta,int siz){
int u=find(sta),v=find(sta+siz+1);
splay(u); splay(v,u); return t[v].c[0];
}
inline void upd(int sta,int tot,int val){
int x=split(sta,tot), y=t[x].f, z=t[y].f;
add(x,val); pu(y); pu(z);
}
inline void rev(int sta,int tot){
int x=split(sta,tot), y=t[x].f, z=t[y].f;
turn(x); pu(y); pu(z);
}
int a[N];
int create(int val){
t[++id]={{0,0},0,0,inf,val,val,1,max(val,0),max(val,0),val};
return id;
}
int build(int l,int r,int f){
if(l>r) return 0;
int mid=(l+r>>1);
int u=create(a[mid]);
t[u].f=f;
t[u].c[0]=build(l,mid-1,u);
t[u].c[1]=build(mid+1,r,u);
pu(u);
return u;
}
inline void ins(int sta,int siz){
int u=find(sta),v=find(sta+1); splay(u); splay(v,u);
t[v].c[0]=build(1,siz,v);
pu(v); pu(u);
}
inline void del(int sta,int siz){
int x=split(sta,siz),y=t[x].f,z=t[y].f;
t[y].c[0]=t[x].f=0; pu(y); pu(z);
}
int n,m;
signed main(){
read(n); read(m);
t[0].mx=-1e4;
create(-1e4);
create(-1e4);
t[1].c[1]=2; t[2].f=1; pu(1);
rot=1;
for(int i=1;i<=n;i++) read(a[i]);
ins(1,n);
for(int i=1;i<=m;i++){
char opt[10]; scanf("%s",opt);
if(opt==act[0]){
int pos,siz; read(pos); read(siz); if(siz==0) continue;
for(int j=1;j<=siz;j++) read(a[j]);
ins(pos+1,siz);
}
else if(opt==act[1]){
int pos,siz; read(pos); read(siz); if(siz==0) continue;
del(pos,siz);
}
else if(opt==act[2]){
int pos,siz,val; read(pos); read(siz); read(val); if(siz==0) continue;
upd(pos,siz,val);
}
else if(opt==act[3]){
int pos,siz; read(pos); read(siz); if(siz==0) continue;
rev(pos,siz);
}
else if(opt==act[4]){
int pos,siz; read(pos); read(siz); if(siz==0){puts("0"); continue;}
int u=split(pos,siz);
printf("%d\n",t[u].s);
}
else{
int u=split(1,t[rot].ct-2);
printf("%d\n",t[u].mx);
}
}
return 0;
}