题目：普通平衡树
参考：
yyb大佬的代码
luogu大佬的题解
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 100000
#define inf (1<<30)struct Node {int val;int cnt;int fa,ch[2];int size;void init() {val=ch[0]=ch[1]=0;cnt=size=1;}
};Node a[maxn+5];
int n=0,rt=0; //节点个数，根节点void pushup(int x) {a[x].size=a[a[x].ch[0]].size+a[a[x].ch[1]].size+a[x].cnt;
}void rotate(int x) { //旋转int y=a[x].fa,z=a[y].fa;int k=(a[y].ch[1]==x); //x是y的哪边儿子a[z].ch[a[z].ch[1]==y]=x,a[x].fa=z;a[y].ch[k]=a[x].ch[k^1],a[a[x].ch[k^1]].fa=y;a[x].ch[k^1]=y,a[y].fa=x;pushup(y),pushup(x);
}void splay(int x,int k) { //伸展while(a[x].fa!=k) {int y=a[x].fa,z=a[y].fa; //父亲和爷爷if(z!=k) {if((a[y].ch[0]==x)^(a[z].ch[0]==y)) rotate(x); //在一条折线else rotate(y); //一条直线}rotate(x);}if(!k) rt=x;
}void insert(int x) { //插入int u=rt,fth=0;while(u&&a[u].val!=x) { //顺着bst往下找插入的位置fth=u; //记录插入位置的父节点u=a[u].ch[x>a[u].val];}if(u) { //存在这个值a[u].cnt++;splay(u,0);return ;}n++; //增加节点总数a[n].init();if(fth) a[fth].ch[x>a[fth].val]=n;a[n].val=x;a[n].fa=fth;splay(n,0); //把最近访问的节点splay到根
}void find(int x) { //查找排名int u=rt;while(a[u].ch[x>a[u].val]&&x!=a[u].val) {u=a[u].ch[x>a[u].val];}splay(u,0);
}int nxt(int x,int k) { //查找前驱/后继find(x);int u=rt;if((a[u].val<x&&!k)||(a[u].val>x&&k)) return u;u=a[u].ch[k];while(a[u].ch[k^1]) u=a[u].ch[k^1];return u;
}void del(int x) { //删除int y=nxt(x,0),z=nxt(x,1);splay(y,0),splay(z,y);int del=a[z].ch[0];if(a[del].cnt>1) {a[del].cnt--;splay(del,0);} else a[z].ch[0]=0;
}int findv(int x) { //查找值int u=rt;while(true) {int y=a[u].ch[0];if(x>a[y].size+a[u].cnt) {x-=a[y].size+a[u].cnt;u=a[u].ch[1];} else if(a[y].size>=x) u=y;else return a[u].val;}
}int main() {int m;scanf("%d",&m);insert(-inf);insert(+inf);while(m--) {int opr,x;scanf("%d%d",&opr,&x);if(opr==1) insert(x);if(opr==2) del(x);if(opr==3) find(x),printf("%d\n",a[a[rt].ch[0]].size);if(opr==4) printf("%d\n",findv(x+1));if(opr==5) printf("%d\n",a[nxt(x,0)].val);if(opr==6) printf("%d\n",a[nxt(x,1)].val);}return 0;
}