萌新求教QAQ,Splay的标记打法那种正确

P3391 【模板】文艺平衡树

lmAKf @ 2019-03-19 19:43:46

为什么这道题的Splay萌新翻了一大片题解都是先下传的标记?

然而我把LCT题解里面的大佬的代码擓过来(先下传标记再Splay)反而WA

大概就是这样: 1:

void Splay(int x, int goal){
    while(t[x].fa != goal){
        pushmark(x);
        int f = t[x].fa, ff = t[f].fa;
        if(ff != goal)
            ((t[f].son[1] == x) ^ (t[ff].son[1] == f)) ? turn(f) : turn(x);
        turn(x);
    }
    if(goal == 0) root = x;
}

2:

void Splay(int x, int goal){
    int top = 0, now = x;
    st[++top] = now;
    while( now != goal ) st[++top] = (now = t[now].fa);
    while( top ) pushmark(st[top--]);
    while( t[x].fa != goal ){
        int f = t[x].fa, ff = t[f].fa;
        if( ff != goal )  ((t[f].son[1] == x) ^ (t[ff].son[1] == f)) ? turn(f) : turn(x);
        turn(x);
    }
    if( goal == 0 ) root = x;
}

by lmAKf @ 2019-03-19 19:44:18

这里turn(x)就是rotate(x),


by zyh2333 @ 2019-03-19 19:50:21

日常膜大佬%%%%%%


by lmAKf @ 2019-03-19 19:51:34

@陌·伤·念·忘 fAKe,某钟神仙不知有多强


by zyh2333 @ 2019-03-19 20:20:18

@Light_Poet哪有你一半


|