block_joker @ 2018-09-18 17:32:41
为什么down操作要放在rotate里而不是spaly里呢? 比如这样能过
inline void rotate(int x) {
int fa=f[x],ac=f[fa];
down(fa),down(x);
int s1=qus(x),s2=qus(fa);
int s=son[x][s1^1];
con(ac,x,s2),con(x,fa,s1^1),con(fa,s,s1);
up(fa),up(x);
}
inline void splay(int x,int pos) {
if(!x)return;
pos=f[pos];
while(f[x]!=pos) {
int fa=f[x],ac=f[fa];
//down(ac),down(fa),down(x);
if(ac!=pos)
qus(fa)^qus(x)?rotate(x):rotate(fa);
rotate(x);
}
if(!pos)root=x;
}
这样不行
inline void rotate(int x) {
int fa=f[x],ac=f[fa];
//down(fa),down(x);
int s1=qus(x),s2=qus(fa);
int s=son[x][s1^1];
con(ac,x,s2),con(x,fa,s1^1),con(fa,s,s1);
up(fa),up(x);
}
inline void splay(int x,int pos) {
if(!x)return;
pos=f[pos];
while(f[x]!=pos) {
int fa=f[x],ac=f[fa];
down(ac),down(fa),down(x);
if(ac!=pos)
qus(fa)^qus(x)?rotate(x):rotate(fa);
rotate(x);
}
if(!pos)root=x;
}
by block_joker @ 2018-09-18 17:32:59
求解答
by ysj1173886760 @ 2018-09-18 17:41:45
@block_joker 没准可以,LCT的pushdown不就是在splay里吗
by ysj1173886760 @ 2018-09-18 17:42:59
@block_joker 应该是先都pushdown,再splay,套个栈,从上到下pushdown一遍再splay
by ysj1173886760 @ 2018-09-18 18:05:54
我好像理解错了你的意思了,抱歉
by block_joker @ 2018-09-19 00:32:59
@ysj1173886760 你的意思是在splay之前,先将含有当前节点的子树都pushdown一次。
可是为什么不能想我的代码写的一样,在rotate之前,先把爷爷,父亲,now,依次pushdown呢。(我提交过代码)
by ysj1173886760 @ 2018-09-19 07:14:08
@block_joker 我昨天晚上模拟了一下,貌似这两种做法得到的结构是不同的,,,但不太明白为什么不对
by block_joker @ 2019-03-18 13:26:43
@ysj1173886760 找到原因了,因为爷爷的父亲也要down一次
by block_joker @ 2019-03-18 13:26:55
此贴完结