[bzoj 3224] Tyvj 1728 普通平衡樹（Splay）

題意：維護一些數，支援這些操作：插入x、删除x、查詢x的排名（多個x則輸出最小者）、查詢排名為x的數、查詢小于x的最大數、查詢大于x的最小數。初始序列為空，操作數不超過10^5，每個數的資料範圍：[-1e7,1e7]。

寫一棵普通的平衡樹就好了。由于是想練習一下Splay Tree，就決定是它了。

以前用指針寫lct，非常難以調試，解決方案是用map把指針映射成數再輸出……自此以後就改用數組了。用結構體數組，意味着要不停地打點加方括号，幹脆不用結構體了，直接數組代碼看起來清爽多了。

旋轉

rot(x, d)

以根和被提上來的兒子方向作為參數。

type(x)

用于獲知結點x是左兒子還是右兒子。

splay(x, p)

操作寫成了循環，是以得記父結點。為了避免忘記這一點，把設定父子關系寫成了

set(x, d, y)

函數。

find(c, b)

操作找小于某數的最大數或大于某數的最小數，并伸展成為根，用一個參數b指明前者還是後者。以前者為例，目前結點小于c，用目前結點更新答案，向右子樹走；否則，向左子樹走。走到空結點

nil

停止。有一個糾結的地方：到達的最深結點y可能不是要求被伸展成為根的結點z，此時怎樣調整樹的結構？後面再說。為了便于處理不存在這樣的數的情況，加兩個虛拟結點

-inf

和

inf

。

insert(c)

插入一個c。先用

find

找到小于c的最大結點并伸展為根，設它為l，r是l的右兒子，斷開l, r，使它們成為新結點的左右兒子，并設新結點為根即可。别忘了用

up(x)

更新子樹大小的資訊。

new_node(c)

用于生成一個新結點，它的值為c，左右子樹為空，大小為1。

erase(c)

删除一個c。先用

find

找到小于c的最大結點并伸展為根，設它為l，r是l的右兒子，找到r樹中最小的結點r’，r’便是待删除的結點。

splay(r', l)

，再把r’的右子樹接到l的右子樹的位置即可。

rank(c)

查詢c的最小排名。x=

find(c, 0)

，傳回小于c的數的個數+1=(x的左子樹大小+1-1)+1=x的左子樹大小+1。别忘了虛拟結點

-inf

。

kth(k)

查詢第k小的數。首先++k，然後在樹上二分即可。

前驅

predecessor(c)

和後繼

successor(c)

有了

find

就很簡單了。查詢，傳回該結點的值即可。

一開始，

find

操作中我把y和z都splay一下，636ms。隻splay(z)是552ms。

寫完之後發覺我的做法好像不太主流……又因為對其複雜度的分析不是很了解，浏覽了一下Sleator和Tarjan的原始論文《Self-adjusting binary search trees》。

關于splay的複雜度。首先，直接放縮成2(r’(x)-r(x))+2是不可行的，因為有常數2。一旦累加起來它就不是常數了，不可忽略；2(r’(x)-r(x))+2 ≤ 3(r’(x)-r(x))要求r’(x)-r(x)≥2，不一定能達成。是說為什麼按照我的了解，把論證中的對數函數換成一切非負的增函數都可以……其二，使用O((m+n)lg n+m)而非O(m lg n+m)，能使複雜度對于一切初始情況皆成立；《算法導論》上說，任何時刻的勢不小于初始的勢，均攤時間才是實際時間的上界，有時的确無法滿足這個條件，也無妨，把勢能的減少量考慮進來即可。

關于insert和erase操作的實作。論文中說：“It is convenient to implement insert and delete using join and split.”又說：“There are alternative implementations of insert and delete that have slightly better amortized time bounds.”前者與我的方法等價，後者是這樣的：

插入直接找待插入的位置，将新結點伸展為根。時間和方法一差不多。

删除直接找待删除的結點，合并左右子樹，替換掉它，把它的父親伸展到根。方法一進行兩三次splay，提到根或根的兒子處；從根的兒子開始go left一次。方法二進行兩次splay，一次提到根，一次提到某結點；從某結點開始go left一次。雖然splay會帶來奇奇怪怪的效果……但是後一種感覺上常數就小一些。

但是犧牲一點時間換代碼簡單也不是特别不劃算……

靈機一動，

find

裡，若y和z不等，就splay(y, z)再splay(z)。這樣處理似乎很科學，複雜度的分析仍然适用（Tarjan他們的access/split操作不存在這樣的問題，主要是因為需求不同）。572ms。

用class進行了一些封裝，看起來很清爽。

#include <cstdio>
#include <cctype>
const int MAX_N = , inf = <<;

class Splay {
    static const int n = MAX_N+, nil = n-;
    int fa[n], ch[n][], v[n], sz[n], ptr, &root;

    void set(int x, int d, int y) { fa[ch[x][d] = y] = x; }
    void up(int x) { sz[x] = sz[ch[x][]] + sz[ch[x][]] + ; }
    int type(int x) { return x == ch[fa[x]][]; }

    int new_node(int c)
    {
        ch[ptr][] = ch[ptr][] = nil;
        v[ptr] = c;
        sz[ptr] = ;
        return ptr++;
    }

    int rot(int x, int d)
    {
        int y = ch[x][d];
        set(fa[x], type(x), y);
        set(x, d, ch[y][d^]);
        set(y, d^, x);
        up(x);
        up(y);
    }

    void splay(int x, int p=)
    {
        int y;
        while ((y = fa[x]) != p) {
            int z = fa[y], t1 = type(x);
            if (z != p) {
                int t2 = type(y);
                if (t1 == t2)
                    rot(z, t2), rot(y, t1);
                else
                    rot(y, t1), rot(z, t2);
            } else
                rot(y, t1);
        }
    }

    int find(int c, int b=)
    {
        int x = root, y, z;
        while (x != nil) {
            y = x;
            if (v[x] != c && v[x] > c == b) {
                z = x;
                x = ch[x][b^];
            } else
                x = ch[x][b];
        }
        if (y != z)
            splay(y, z);
        splay(z);
        return z;
    }

    public:

    Splay(): ptr(), root(ch[][])
    {
        sz[nil] = ;
        set(, , new_node(-inf));
        set(, , new_node(inf));
        up();
    }

    void insert(int c)
    {
        int l = find(c), r = ch[l][], x = new_node(c);
        ch[l][] = nil;
        set(, , x);
        set(x, , l);
        set(x, , r);
        up(l);
        up(x);
    }

    void erase(int c)
    {
        int l = find(c), r = ch[l][];
        while (ch[r][] != nil)
            r = ch[r][];
        splay(r, l);
        set(l, , ch[r][]);
        up(l);
    }

    int predecessor(int c)
    {
        return v[find(c)];
    }

    int successor(int c)
    {
        return v[find(c, )];
    }

    int rank(int c)
    {
        return sz[ch[find(c)][]] + ;
    }

    int kth(int k)
    {
        ++k;
        int x = root;
        while (x != nil) {
            int s = sz[ch[x][]];
            if (s+ == k)
                return splay(x), v[x];
            if (s >= k)
                x = ch[x][];
            else
                k -= s+, x = ch[x][];
        }
    }
} T;

template<typename t>
inline void read(t& x)
{
    char c = getchar();
    int sgn = ;
    x = ;
    while (!isdigit(c)) {
        sgn = c == '-' ? - : ;
        c = getchar();
    }
    while (isdigit(c)) {
        x = x* + c - '0';
        c = getchar();
    }
    x *= sgn;
}

int main()
{
    int n;
    read(n);
    while (n--) {
        int opt, x;
        read(opt), read(x);
        switch (opt) {
            case :
                T.insert(x); break;
            case :
                T.erase(x); break;
            case :
                printf("%d\n", T.rank(x)); break;
            case :
                printf("%d\n", T.kth(x)); break;
            case :
                printf("%d\n", T.predecessor(x)); break;
            case :
                printf("%d\n", T.successor(x));
        }
    }
    return ;
}