【模板】可持久化平衡树

如题，这是一个模板。。。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>

inline void read(int & x)
{
    int k = 1; x = 0;
    char c = getchar();
    while (!isdigit(c))
        if (c == '-') c = getchar(), k = -1;
        else c = getchar();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48),
        c = getchar();
    x *= k; 
}

const int MAXN = 3e7 + 999;
int seed(1024), m, tot(0), opt, st, ed, las, x, y;
int siz[MAXN], val[MAXN], rnd[MAXN], son[MAXN][2], root[MAXN];

inline int Rand(void)
{
    return seed = (int)seed * 482711LL % 2147483647;
}

inline void Pushup(int u)
{
    if (u) siz[u] = siz[son[u][1]] + siz[son[u][0]] + 1; 
}

inline int Copy(int u)
{
    ++tot;
    val[tot] = val[u];
    siz[tot] = siz[u];
    rnd[tot] = rnd[u];
    son[tot][0] = son[u][0];
    son[tot][1] = son[u][1];
    return tot;
}

inline int New(int x)
{
    ++tot;
    val[tot] = x;
    siz[tot] = 1;
    rnd[tot] = Rand();
    son[tot][1] = son[tot][0] = 0;
    return tot;
}

inline void Split(int u, int x, int &a, int &b)
{
    if (!u) { a = b = 0; return; }
    if (val[u] <= x) a = Copy(u), Split(son[a][1], x, son[a][1], b);
    else b = Copy(u), Split(son[b][0], x, a, son[b][0]);     
    Pushup(a); Pushup(b);    
}

inline void Merge(int &u, int a, int b)
{
    if (!a || !b) { u = a | b; return; }
    if (rnd[a] < rnd[b]) u = Copy(a), Merge(son[u][1], son[u][1], b);
    else u = Copy(b), Merge(son[u][0], a, son[u][0]);  
    Pushup(u);
}

inline int Findkth(int u, int k)
{
    while (siz[son[u][0]] + 1 != k && u)
        if (siz[son[u][0]] >= k) u = son[u][0];
        else k -= siz[son[u][0]] + 1, u = son[u][1];
    return u;
}

inline void Insert(int u, int x) 
{
    int a(0), b(0), c(0);
    Split(root[u], x, a, b);
    c = New(x);
    Merge(a, a, c);
    Merge(root[u], a, b);
}

inline void Delete(int u, int x)
{
    int a(0), b(0), c(0);
    Split(root[u], x, a, b);
    Split(a, x - 1, a, c);
    Merge(c, son[c][0], son[c][1]);
    Merge(a, a, c);
    Merge(root[u], a, b);
}

inline void Getrank(int u, int x)
{
    int a(0), b(0), c(0);
    Split(root[u], x - 1, a, b);
    printf("%d
", siz[a] + 1);
    Merge(root[u], a, b); 
}

inline void Getkth(int u, int k)
{
    printf("%d
", val[Findkth(root[u], k)]);
}

inline void Pre(int u, int x)
{
    int a(0), b(0), c(0);
    Split(root[u], x - 1, a, b);
    if (!a) puts("-2147483647");
    else printf("%d
", val[Findkth(a, siz[a])]);
    Merge(root[u], a, b);
}

inline void Suf(int u, int x)
{
    int a(0), b(0), c(0);
    Split(root[u], x, a, b);
    if (!b) puts("2147483647");
    else printf("%d
", val[Findkth(b, 1)]);
    Merge(root[u], a, b);
}

signed main()
{
    read(m); 
    for (int i = 1; i <= m; ++i)
    {
        read(las), read(opt), read(x);
        root[i] = root[las];
        if (opt == 1) Insert(i, x);
        if (opt == 2) Delete(i, x);
        if (opt == 3) Getrank(i, x);
        if (opt == 4) Getkth(i, x);
        if (opt == 5) Pre(i, x);
        if (opt == 6) Suf(i, x);
    }
    return 0;
}