替罪羊树（AI调过：

#include <iostream>
#define N 1000010
#define alpha 0.75
using namespace std;

struct node{
    int ls,rs;
    int val;
    int tot;
    int size;
    int del;
}t[N];

int order[N],cnt;
int tree_stack[N],top = 0;
int root = 0;

void inorder(int u){
    if(!u) return;
    inorder(t[u].ls);
    if(t[u].del) order[++cnt] = u;
    else tree_stack[++top] = u;
    inorder(t[u].rs);
}

void Initnode(int u){
    t[u].ls = t[u].rs = 0;
    // FIXED
    t[u].size = t[u].tot = 1;
    t[u].del = 0;
}

void Update(int u){
    t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
    t[u].tot = t[t[u].ls].tot + t[t[u].rs].tot + 1;
}

void build(int l,int r,int &u){
    int mid = (l + r) >> 1;
    u = order[mid];
    if(l == r){Initnode(u);return;}
    if(l < mid) build(l,mid - 1,t[u].ls);
    if(l == mid) t[u].ls = 0;
    build(mid + 1,r,t[u].rs);
    Update(u);
}

void rebuild(int &u){
    cnt = 0;
    inorder(u);
    if(cnt) build(1,cnt,u);
    else u = 0;
}

bool notbalance(int u){
    // if((double)t[u].size * alpha <= (double)max(t[t[u].ls].size,t[t[u].rs].size))
    //     return true;
    // return false;
    int left_size = t[t[u].ls].size;
    int right_size = t[t[u].rs].size;
    return (double)left_size > (double)t[u].size * alpha || (double)right_size > (double)t[u].size * alpha;
}

void Insert(int &u,int x){
    if(!u){
        u = tree_stack[top--];
        t[u].val = x;
        Initnode(u);
        return;
    }
    t[u].size++;
    t[u].tot++;
    if(t[u].val >= x) Insert(t[u].ls,x);
    else Insert(t[u].rs,x);
    if(notbalance(u)) rebuild(u);
}

int Rank(int u, int x) {
    if(u == 0) return 0;
    if(x > t[u].val) return t[t[u].ls].size + t[u].del + Rank(t[u].rs,x);
    return Rank(t[u].ls,x);
}

int kth(int k){
    int u = root;
    while(u){
        if(!t[u].del && t[t[u].ls].size + 1 == k) return t[u].val;
        else if(t[t[u].ls].size >= k) u = t[u].ls;
        else{
            // k -= t[t[u].ls].size + t[u].del;
            k -= t[t[u].ls].size + (t[u].del ? 1 : 0); // FIXED
            u = t[u].rs;
        }
    }
    return -1;
}


void Del_k(int &u,int k){
    t[u].size--;
    if(t[t[u].ls].size + 1 == k){
        t[u].del = 1;           // FIXED
        return;
    }
    if(t[t[u].ls].size + t[u].del >= k) Del_k(t[u].ls,k);
    else Del_k(t[u].rs,k - t[t[u].ls].size - t[u].del);
}

void Del(int x){
    Del_k(root,Rank(root,x) + 1);
    if(t[root].tot * alpha >= t[root].size) rebuild(root);
}

int predecessor(int u, int x) {
    int last = -1; // 用于存储前驱
    while (u) {
        if (t[u].val < x) {
            last = t[u].val; // 更新前驱
            u = t[u].rs; // 向右子树查找
        } else {
            u = t[u].ls; // 向左子树查找
        }
    }
    return last; // 返回前驱
}

int successor(int u, int x) {
    int last = -1; // 用于存储后继
    while (u) {
        if (t[u].val > x) {
            last = t[u].val; // 更新后继
            u = t[u].ls; // 向左子树查找
        } else {
            u = t[u].rs; // 向右子树查找
        }
    }
    return last; // 返回后继
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    for(int i = N - 1;i >= 1;i--) tree_stack[++top] = i;
    int q;
    cin >> q;
    while(q--){
        int op,x;
        cin >> op >> x;
        switch(op){
        case 1:Insert(root,x);break;
        case 2:Del(x);break;
        case 3:cout << Rank(root,x) + 1 << '\n';break;
        case 4:cout << kth(x) << '\n';break;
        // case 5:cout << kth(Rank(root,x)) << '\n';break;
        // case 6:cout << kth(Rank(root,x + 1) + 1) << '\n';break;
        case 5: cout << predecessor(root, x) << '\n'; break; // 查询前驱
        case 6: cout << successor(root, x) << '\n'; break; // 查询后继

        }
    }
    return 0;
}

Treap树：

#include <iostream>
#include <ctime>
#define M 1000010
using namespace std;

int cnt = 0;

struct Node{
    int ls,rs;
    int key,pri;
    int size;
}t[M];

void newNode(int x){
    cnt++;
    t[cnt].size = 1;
    t[cnt].ls = t[cnt].rs = 0;
    t[cnt].key = x;
    t[cnt].pri = rand();
}

void Update(int u){
    t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
}

void rotate(int &o,int d){
    int k;
    if(d == 1){
        k = t[o].rs;
        t[o].rs = t[k].ls;
        t[k].ls = o;
    }else{
        k = t[o].ls;
        t[o].ls = t[k].rs;
        t[k].rs = o;
    }
    t[k].size = t[o].size;
    Update(o);
    o = k;
}

void Insert(int &u,int x){
    if(u == 0){newNode(x);u = cnt;return;}
    t[u].size++;
    if(u >= t[u].key) Insert(t[u].rs,x);
    else Insert(t[u].ls,x);
    if(t[u].ls != 0 && t[u].pri > t[t[u].ls].pri) rotate(u,0);
    if(t[u].rs != 0 && t[u].pri > t[t[u].rs].pri) rotate(u,1);
    Update(u);
}

void Del(int &u,int x){
    t[u].size--;
    if(t[u].key == x){
        if(t[u].ls == 0 && t[u].rs == 0){u = 0;return;}
        if(t[u].ls == 0 || t[u].rs == 0){u = t[u].ls + t[u].rs;return;}
        if(t[t[u].ls].pri < t[t[u].rs].pri){rotate(u,0);Del(t[u].rs,x);return;}
        else{rotate(u,1);Del(t[u].ls,x);return;}
    }
    if(t[u].key >= x) Del(t[u].ls,x);
    else Del(t[u].rs,x);
    Update(u);
}

int Rank(int u,int x){
    if(u == 0) return 0;
    if(x > t[u].key) return t[t[u].ls].size + 1 + Rank(t[u].rs,x);
    return Rank(t[u].ls,x);
}

int kth(int u,int k){
    if(k == t[t[u].ls].size + 1) return t[u].key;
    if(k > t[t[u].ls].size + 1) return kth(t[u].rs,k - t[t[u].ls].size) - 1;
    if(k <= t[t[u].ls].size) return kth(t[u].ls,k);
    return 0;
}

int Precursor(int u,int x){
    if(u == 0) return 0;
    if(t[u].key >= x) return Precursor(t[u].ls,x);
    int tmp = Precursor(t[u].rs,x);
    if(tmp == 0) return t[u].key;
    return tmp;
}

int Succursor(int u,int x){
    if(u == 0) return 0;
    if(t[u].key <= x) return Succursor(t[u].rs,x);
    int tmp = Succursor(t[u].ls,x);
    if(tmp == 0) return t[u].key;
    return tmp;
}

int main(){
    srand(time(nullptr));
    int root = 0;
    int n;
    cin >> n;
    while(n--){
        int op,x;
        cin >> op >> x;
        switch(op){
        case 1:Insert(root,x);break;
        case 2:Del(root,x);break;
        case 3:cout << Rank(root,x) + 1 << '\n';break;
        case 4:cout << kth(root,x) << '\n';break;
        case 5:cout << Precursor(root,x) << '\n';break;
        case 6:cout << Succursor(root,x) << '\n';break;
        }
    }
    return 0;
}

FHQ Treap树：

#include <iostream>
#include <ctime>
#define M 1000010
using namespace std;

int cnt = 0,root = 0;

struct Node{
    int ls,rs;
    int key,pri;
    int size;
}t[M];

void newNode(int x){
    cnt++;
    t[cnt].size = 1;
    t[cnt].ls = t[cnt].rs = 0;
    t[cnt].key = x;
    t[cnt].pri = rand();
}

void Update(int u){
    t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
}

void Split(int u,int x,int &L,int &R){
    if(u == 0){L = R = 0;return;}
    if(t[u].key <= x){
        L = u;
        Split(t[u].rs,x,t[u].rs,R);
    }else{
        R = u;
        Split(t[u].ls,x,L,t[u].ls);
    }
    Update(u);
}

int Merge(int L,int R){
    if(L == 0 || R == 0) return L + R;
    if(t[L].pri > t[R].pri){
        t[L].rs = Merge(t[L].rs,R);
        Update(L);
        return L;
    }else{
        t[R].ls = Merge(L,t[R].ls);
        Update(R);
        return R;
    }
}

void Insert(int x){
    int L,R;
    Split(root,x,L,R);
    newNode(x);
    int aa = Merge(L,cnt);
    root = Merge(aa,R);
}

void Del(int x){
    int L,R,p;
    Split(root,x,L,R);
    Split(L,x - 1,L,p);
    p = Merge(t[p].ls,t[p].rs);
    root = Merge(Merge(L,p),R);
}

void Rank(int x){
    int L,R;
    Split(root,x - 1,L,R);
    cout << t[L].size + 1 << '\n';
    root = Merge(L,R);
}

int kth(int u,int k){
    if(k == t[t[u].ls].size + 1) return u;
    if(k > t[t[u].ls].size + 1) return kth(t[u].ls,k);
    if(k <= t[t[u].ls].size) return kth(t[u].rs,k - t[t[u].ls].size - 1);
    return 0;
}

void Precursor(int x){
    int L,R;
    Split(root,x - 1,L,R);
    cout << t[kth(L,t[L].size)].key << '\n';
    root = Merge(L,R);
}

void Succursor(int x){
    int L,R;
    Split(root,x,L,R);
    cout << t[kth(R,1)].key << '\n';
    root = Merge(L,R);
}

int main(){
    srand(time(nullptr));
    int n;
    cin >> n;
    while(n--){
        int op,x;
        cin >> op >> x;
        switch(op){
        case 1:Insert(x);break;
        case 2:Del(x);break;
        case 3:Rank(x);break;
        case 4:cout << t[kth(root,x)].key << '\n';break;
        case 5:Precursor(x);break;
        case 6:Succursor(x);break;
        }
    }
    return 0;
}