求助 LCT 中 rotate 的写法
查看原帖
求助 LCT 中 rotate 的写法
207393
OshamaScramble楼主2022/2/19 17:23

如题,之前写 splay 一直使用是在 rotate 中下传标记的写法,大概长这样:

void rotate(int x){
	if(!isr(x))pdown(fa[x]);
	pdown(x);
	int y=fa[x],z=fa[y],k=get(x);
	if(!isr(y))ch[z][get(y)]=x;
	ch[y][k]=ch[x][!k],fa[y]=x;
	if(ch[x][!k])fa[ch[x][!k]]=y;
	ch[x][!k]=y,fa[x]=z,pup(y),pup(x);
}

其中 pdown 是下传标记, isr 是判定是否为根。但这种写法在 LCT 中是错误的,题解的米娜桑都写了类似于 pushall 来依次下传根到当前节点的所有标记。

小萌新觉得已经判掉根的情况了,并不知道这种写法错在哪里,所以发帖请求大佬的帮助!

2022/2/19 17:23
加载中...