Splay TLE 5~12 WA13求调

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 5;
#define ls t[u].ch[0]
#define rs t[u].ch[1]

int root, tot;

struct node {
    int ch[2];
    int fa, val, siz;
} t[maxn];

void init(int &u, int fa, int val) {
    u = ++tot;
    t[u].val = val;
    t[tot].fa = fa;
    t[tot].siz = 1;
}

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

bool ident(int u, int fa) { 
    return t[fa].ch[1] == u; 
}

void connect(int u, int fa, int d) { 
    t[fa].ch[d] = u;
    t[u].fa = fa;
}

void rotate(int u) {
    int f = t[u].fa, fa = t[f].fa, k = ident(u, f);
    connect(t[u].ch[k ^ 1], f, k);
    connect(u, fa, ident(f, fa));
    connect(f, u, k ^ 1);
    push_up(f);
    push_up(u);
}

void splaying(int u, int top) {   
    if (!top) {
        root = u;
    }
    for (; t[u].fa != top;) {
        int f = t[u].fa, fa = t[f].fa;
        if (fa != top) {  
            if (ident(f, fa) ^ ident(u, f)) {
                rotate(u);
            } else {
                rotate(f);
            }
        }
        rotate(u);   
    }
}

void add(int &u, int val, int fa) {
    if (!u) {
        init(u, fa, val);
        splaying(u, 0);  
    } else if (val < t[u].val) {
        add(t[u].ch[0], val, u);
    } else {
        add(t[u].ch[1], val, u);
    }
}

void detach(int &u, int val) {
    if (val == t[u].val) {
        splaying(u, 0);
        if (rs) {
            int p = rs;
            while (t[p].ch[0]) {   
                p = t[p].ch[0];
            }
            splaying(p, u);  
            connect(ls, p, 0);   
            root = p;
            t[p].fa = 0;   
            push_up(root);
        } else {
            root = ls;
            t[root].fa = 0;
        }
    } else if (val < t[u].val) {
        detach(ls, val);
    } else {
        detach(rs, val);
    }
}

int get_rank(int val) {
    int u = root, rk = 1, pre = 0;
    while (u) {
        if (val <= t[u].val) {
            pre = u;
            u = ls;
        } else {
            rk += t[ls].siz + 1;
            u = rs;
        }
    }
    if (pre) {   
        splaying(pre, 0);
    }
    return rk;
}

int query(int k){   //真 简单
    int u = root;
    while(u){
        if(t[ls].siz + 1 == k){
            splaying(u, 0);
            break;
        }
        else if(t[ls].siz >= k){
            u = t[u].ch[0];
        }
        else{
            k -= t[ls].siz + 1;
            u = rs;
        }
    }
    return t[u].val;
}

void best_coder() {
    int n;
    cin >> n;
    while(n--){
        int op;
        cin >> op;
        if(op == 1){
            int x;
            cin >> x;
            add(root, x, 0);
        }
        else if(op == 2){
            int x;
            cin >> x;
            detach(root, x);
        }
        else if(op == 3){
            int x;
            cin >> x;
            cout << get_rank(x) << '\n';
        }
        else if(op == 4){
            int x;
            cin >> x;
            cout << query(x) << '\n';
        }
        else if(op == 5){
            int x;
            cin >> x;
            cout << query(get_rank(x) - 1) << '\n';
        }
        else{
            int x;
            cin >> x;
            cout << query(get_rank(x + 1)) << '\n';
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    best_coder();


    return 0;
}