Treap树学习笔记

enum {
    Maxn = 1000005
};

struct FHQTreap {
    int lson[Maxn], rson[Maxn], data[Maxn];
    int rnd[Maxn], sze[Maxn], root, tot, seed;
    FHQTreap(void) {
        Ms(lson, 0), Ms(rson, 0), Ms(data, 0);
        Ms(rnd, 0), Ms(sze, 0), root = tot = 0, seed = 1;
    }

    inline int _rand(void) { return seed *= 482711; }
    inline void pushup(int pos) { sze[pos] = sze[lson[pos]] + sze[rson[pos]] + 1; }
    inline void split(int pos, int val, int &x, int &y) {
        if (!pos) { x = y = 0; return; }
        if (data[pos] <= val) x = pos, split(rson[pos], val, rson[pos], y);
        else y = pos, split(lson[pos], val, x, lson[pos]); pushup(pos);
    }

    inline int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (rnd[x] < rnd[y]) return rson[x] = merge(rson[x], y), pushup(x), x;
        else return lson[y] = merge(x, lson[y]), pushup(y), y;
    }

    inline void insert(int val) {
        int x, y, pos = ++tot;
        data[pos] = val, sze[pos] = 1, rnd[pos] = _rand();
        split(root, val, x, y);
        root = merge(merge(x, pos), y);
    }

    inline void remove(int val) {
        int x, y, z;
        split(root, val - 1, x, y);
        split(y, val, y, z); if (!y) return;
        y = merge(lson[y], rson[y]);
        root = merge(x, merge(y, z));
    }

    inline int query_rank(int val) {
        int x, y, ret;
        split(root, val - 1, x, y);
        ret = sze[x] + 1; root = merge(x, y);
        return ret;
    }

    inline int select(int kth) {
        int pos = root;
        while (kth != sze[lson[pos]] + 1)
            if (kth <= sze[lson[pos]]) pos = lson[pos];
            else kth -= sze[lson[pos]] + 1, pos = rson[pos];
        return data[pos];
    }

    inline int pred(int val) { return select(query_rank(val) - 1); }
    inline int succ(int val) { return select(query_rank(val + 1)); }
} treap;

# include <bits/stdc++.h> # define int long long
using namespace std; int ans; struct STL_Treap{ vector<int>a; void insert(int x) { a.insert(lower_bound(a.begin(),a.end(),x),x);} void erase(int x) {a.erase(lower_bound(a.begin(),a.end(),x));} int rank(int x) {return lower_bound(a.begin(),a.end(),x)-a.begin()+1;} int kth(int x){return a[x-1];} int pre(int x) {return *(--lower_bound(a.begin(),a.end(),x));} int nxt(int x){return *upper_bound(a.begin(),a.end(),x);} }treap; signed main() { scanf("%lld",&ans); for (int i=1;i<=ans;i++) { int a,b; scanf("%lld%lld",&a,&b); switch (a) { case 1ll:treap.insert(b);break; case 2ll:treap.erase(b);break; case 3ll:cout<<treap.rank(b)<<'\n';break; case 4ll:cout<<treap.kth(b)<<'\n';break; case 5ll:cout<<treap.pre(b)<<'\n';break; case 6ll:cout<<treap.nxt(b)<<'\n';break; } } return 0; }