spaly竟然和splay一样快!!!!!!

P3391 【模板】文艺平衡树

h__a_ny @ 2017-07-17 09:50:00

spaly:

void spaly(node* &o , int k)
{
    pushdown(o);
    int d = cmp(o , k);
    if (d == 1)
        k -= o -> ch[0] -> s + 1;
    if (d != -1)
    {
        spaly(o -> ch[d] , k);
        rotate(o , d ^ 1);
    }
}

splay:

void splay(node* &o , int k)
{
    pushdown(o);
    int d = cmp(o , k);
    if (d == 1)
        k -= o -> ch[0] -> s + 1;
    if (d != -1)
    {
        node *p = o -> ch[d];
        pushdown(p);
        int d2 = cmp(p , k);
        int k2 = k;
        if (d2 == 1)
            k2 -= p -> ch[0] -> s + 1;
        if (d2 != -1)
        {
            splay(p -> ch[d2] , k2);
            if (d == d2)
                rotate(o , d ^ 1);
            else
                rotate(o -> ch[d] , d);
        }
        rotate(o , d ^ 1);
    }
}

不可思议,匪夷所思!!!!! 是不是洛谷数据太水了


by fighter_OI @ 2017-10-01 22:56:14

@rushcheyo 太强啦


by rushcheyo @ 2017-10-01 23:22:03

@zzh2003214 您是哪位?


by rushcheyo @ 2017-10-01 23:22:28

@zzh2003214 不好意思我zz了


上一页 |