一个问题

P3391 【模板】文艺平衡树

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

此贴完结


|