洛谷【P3369】普通平衡树(AVL树做法)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct node{
    int l, r, val, height, size;
}tree[maxn];
int t, tot, root;

inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void print(int x){
    if(x < 0) x = ~x + 1, putchar('-');
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

inline void newnode(int &now, int val){
    tree[now=++tot].val = val;
    tree[tot].size = 1;
}

inline void update(int now){
    tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
    tree[now].height = max(tree[tree[now].l].height, tree[tree[now].r].height) + 1;
}

inline int factor(int now){///获取平衡因子
    return tree[tree[now].l].height - tree[tree[now].r].height;
}

inline void lrotate(int &now){///左旋
    int r = tree[now].r;
    tree[now].r = tree[r].l;
    tree[r].l = now;
    now = r;
    update(tree[now].l), update(now);
}

inline void rrotate(int &now){///右旋
    int l = tree[now].l;
    tree[now].l = tree[l].r;
    tree[l].r = now;
    now = l;
    update(tree[now].r), update(now);
}

inline void check(int &now){
    int nf = factor(now);
    if(nf > 1){
        int lf = factor(tree[now].l);
        if(lf > 0) rrotate(now);                      ///LL
        else lrotate(tree[now].l), rrotate(now);      ///LR
    }
    else if(nf < -1){
        int rf = factor(tree[now].r);
        if(rf < 0) lrotate(now);                      ///RR
        else rrotate(tree[now].r), lrotate(now);      ///RL
    }
    else if(now) update(now);
}

void ins(int &now, int val){
    if(!now) newnode(now, val);
    else if(val < tree[now].val) ins(tree[now].l, val);
    else ins(tree[now].r, val);
    check(now);
}

int find(int &now, int fa){///找到要删除节点的后继
    int ret;
    if(!tree[now].l){
        ret = now;
        tree[fa].l = tree[now].r;
    }
    else{
        ret = find(tree[now].l, now);
        check(now);
    }
    return ret;
}

void del(int &now, int val){
    if(val == tree[now].val){
        int l = tree[now].l, r = tree[now].r;
        if(!l || !r) now = l + r;
        else{
            now = find(r, r);
            if(now!=r) tree[now].r = r;
            tree[now].l = l;
        }
    }
    else if(val < tree[now].val) del(tree[now].l, val);
    else del(tree[now].r, val);
    check(now);
}

int getrank(int val){
    int now = root, rank = 1;
    while(now){
        if(val <= tree[now].val) now=tree[now].l;
        else{
            rank += tree[tree[now].l].size + 1;
            now = tree[now].r;
        }
    }
    return rank;
}

int getnum(int rank){
    int now = root;
    while(now){
        if(tree[tree[now].l].size + 1 == rank) break;
        else if(tree[tree[now].l].size >= rank) now=tree[now].l;
        else{
            rank -= tree[tree[now].l].size + 1;
            now = tree[now].r;
        }
    }
    return tree[now].val;
}

int main(){
    t = read();
    while(t--){
        int op, x;
        op = read(), x = read();
        if(op == 1) ins(root, x);
        else if(op == 2) del(root, x);
        else if(op == 3) print(getrank(x)), putchar('\n');
        else if(op == 4) print(getnum(x)), putchar('\n');
        else if(op == 5) print(getnum(getrank(x) - 1)), putchar('\n');
        else print(getnum(getrank(x + 1))), putchar('\n');
    }
    
    return 0;
}
/*
* ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
* └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
* │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/