模板 - 无旋Treap-程序员宅基地

普通平衡树：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls(p) ch[p][0]
#define rs(p) ch[p][1]

const int MAXN = 100000 + 5;
int val[MAXN], ch[MAXN][2], rnd[MAXN], siz[MAXN], tot, root;

void Init() {
    tot = root = 0;
}

void PushUp(int p) {
    siz[p] = siz[ls(p)] + siz[rs(p)] + 1;
}

void SplitValue(int p, int v, int &x, int &y) {
    if(!p) {
        x = y = 0;
        return;
    }
    if(v < val[p]) {
        y = p;
        SplitValue(ls(p), v, x, ls(p));
        PushUp(y);
    } else {
        x = p;
        SplitValue(rs(p), v, rs(p), y);
        PushUp(x);
    }
}

void SplitRank(int p, int rk, int &x, int &y) {
    if(!p) {
        x = y = 0;
        return;
    }
    if(rk <= siz[ls(p)]) {
        y = p;
        SplitRank(ls(p), rk, x, ls(p));
        PushUp(y);
    } else {
        x = p;
        SplitRank(rs(p), rk - siz[ls(p)] - 1, rs(p), y);
        PushUp(x);
    }
}

int Merge(int x, int y) {
    if(!x || !y)
        return x | y;
    if(rnd[x] < rnd[y]) {
        rs(x) = Merge(rs(x), y);
        PushUp(x);
        return x;
    } else {
        ls(y) = Merge(x, ls(y));
        PushUp(y);
        return y;
    }
}

int NewNode(int v) {
    ++tot;
    ch[tot][0] = ch[tot][1] = 0;
    val[tot] = v, rnd[tot] = rand();
    siz[tot] = 1;
    return tot;
}

void Insert(int &root, int v) {
    int x = 0, y = 0;
    SplitValue(root, v, x, y);
    root = Merge(Merge(x, NewNode(v)), y);
}

void Remove(int &root, int v) {
    int x = 0, y = 0, z = 0;
    SplitValue(root, v, x, z);
    SplitValue(x, v - 1, x, y);
    y = Merge(ls(y), rs(y));
    root = Merge(Merge(x, y), z);
}

int GetRank(int &root, int v) {
    int x = 0, y = 0;
    SplitValue(root, v - 1, x, y);
    int rk = siz[x] + 1;
    root = Merge(x, y);
    return rk;
}

int GetValue(int &root, int rk) {
    int x = 0, y = 0, z = 0;
    SplitRank(root, rk, x, z);
    SplitRank(x, rk - 1, x, y);
    int v = val[y];
    root = Merge(Merge(x, y), z);
    return v;
}

int GetPrev(int &root, int v) {
    int x = 0, y = 0;
    SplitValue(root, v - 1, x, y);
    int prev = GetValue(x, siz[x]);
    root = Merge(x, y);
    return prev;
}

int GetNext(int &root, int v) {
    int x = 0, y = 0;
    SplitValue(root, v, x, y);
    int next = GetValue(y, 1);
    root = Merge(x, y);
    return next;
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int n;
    scanf("%d", &n);
    Init();
    for(int i = 1; i <= n; ++i) {
        int op, x;
        scanf("%d%d", &op, &x);
        switch(op) {
            case 1:
                Insert(root, x);
                break;
            case 2:
                Remove(root, x);
                break;
            case 3:
                printf("%d\n", GetRank(root, x));
                break;
            case 4:
                printf("%d\n", GetValue(root, x));
                break;
            case 5:
                printf("%d\n", GetPrev(root, x));
                break;
            case 6:
                printf("%d\n", GetNext(root, x));
                break;
        }
    }
    return 0;
}

Treap的O(n)建树和回收：

//O(n)建树，返回新树的根
int st[MAXN], stop;
char buf[MAXN];
inline int Build(int n) {
    stop = 0;
    for(int i = 0; i < n; ++i) {
        int tmp = NewNode(buf[i]), last = 0;
        while(stop && rnd[st[stop]] > rnd[tmp]) {
            last = st[stop];
            PushUp(last);
            st[stop--] = 0;
        }
        if(stop)
            rs(st[stop]) = tmp;
        ls(tmp) = last;
        st[++stop] = tmp;
    }
    while(stop)
        PushUp(st[stop--]);
    return st[1];
}

//O(n)回收整棵树
inline void UnBuild(int p) {
    if(!p)
        return;
    UnBuild(ls(p));
    UnBuild(rs(p));
    RecBin.push(p);
}

非递归的不带修改的查询，方便可持久化：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls(p) ch[p][0]
#define rs(p) ch[p][1]

const int MAXN = 100000 + 5;
int val[MAXN], ch[MAXN][2], rnd[MAXN], siz[MAXN], tot, root;

void Init() {
    tot = root = 0;
}

void PushUp(int p) {
    siz[p] = siz[ls(p)] + siz[rs(p)] + 1;
}

void SplitValue(int p, int v, int &x, int &y) {
    if(!p) {
        x = y = 0;
        return;
    }
    if(v < val[p]) {
        y = p;
        SplitValue(ls(p), v, x, ls(p));
        PushUp(y);
    } else {
        x = p;
        SplitValue(rs(p), v, rs(p), y);
        PushUp(x);
    }
}

void SplitRank(int p, int rk, int &x, int &y) {
    if(!p) {
        x = y = 0;
        return;
    }
    if(rk <= siz[ls(p)]) {
        y = p;
        SplitRank(ls(p), rk, x, ls(p));
        PushUp(y);
    } else {
        x = p;
        SplitRank(rs(p), rk - siz[ls(p)] - 1, rs(p), y);
        PushUp(x);
    }
}

int Merge(int x, int y) {
    if(!x || !y)
        return x | y;
    if(rnd[x] < rnd[y]) {
        rs(x) = Merge(rs(x), y);
        PushUp(x);
        return x;
    } else {
        ls(y) = Merge(x, ls(y));
        PushUp(y);
        return y;
    }
}

int NewNode(int v) {
    ++tot;
    ch[tot][0] = ch[tot][1] = 0;
    val[tot] = v, rnd[tot] = rand();
    siz[tot] = 1;
    return tot;
}

void Insert(int &root, int v) {
    int x = 0, y = 0;
    SplitValue(root, v, x, y);
    root = Merge(Merge(x, NewNode(v)), y);
}

void Remove(int &root, int v) {
    int x = 0, y = 0, z = 0;
    SplitValue(root, v, x, z);
    SplitValue(x, v - 1, x, y);
    y = Merge(ls(y), rs(y));
    root = Merge(Merge(x, y), z);
}

int GetRank2(int p, int v) {
    int rk = 1;
    while(p) {
        if(v < val[p])
            p = ls(p);
        else if(v == val[p])
            p = ls(p);
        else {
            rk += siz[ls(p)] + 1;
            p = rs(p);
        }
    }
    return rk;
}

int GetValue2(int p, int rk) {
    while(p) {
        if(rk <= siz[ls(p)])
            p = ls(p);
        else if(rk == siz[ls(p)] + 1)
            return val[p];
        else {
            rk -= siz[ls(p)] + 1;
            p = rs(p);
        }
    }
}

int GetPrev2(int p, int v) {
    int prev;
    while(p) {
        if(v <= val[p])
            p = ls(p);
        else {
            prev = val[p];
            p = rs(p);
        }
    }
    return prev;
}

int GetNext2(int p, int v) {
    int next;
    while(p) {
        if(v < val[p]) {
            next = val[p];
            p = ls(p);
        } else
            p = rs(p);
    }
    return next;
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int n;
    scanf("%d", &n);
    Init();
    for(int i = 1; i <= n; ++i) {
        int op, x;
        scanf("%d%d", &op, &x);
        switch(op) {
            case 1:
                Insert(root, x);
                break;
            case 2:
                Remove(root, x);
                break;
            case 3:
                printf("%d\n", GetRank2(root, x));
                break;
            case 4:
                printf("%d\n", GetValue2(root, x));
                break;
            case 5:
                printf("%d\n", GetPrev2(root, x));
                break;
            case 6:
                printf("%d\n", GetNext2(root, x));
                break;
        }
    }
    return 0;
}