关于懒标记下传
查看原帖
关于懒标记下传
456415
ckain楼主2022/8/31 23:33

如题,只在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;
}
2022/8/31 23:33
加载中...