前序，中序，后序，中双序，中双后序，前中双序，前中双后序，前后序，前中后序，前中序，中后序，前中后序平衡树
首先，请阅读这篇文章
这篇文章已经介绍了中双序（维护中间的两个值），前序，中序平衡树。
既然我们已经会了前序，后序是显然的。
如果我们将前序，中双序，中序，后序结合起来，就可以发明标题中的 8 种剩下的平衡树。
具体来说，这些东西就是如果名字里有前，维护最小值，有后维护最大值，有中双维护 mid 的前驱和后继，有中维护 mid 的前驱或后继。
在这里，给出前中双后序平衡树的参考实现，其他平衡树你删一删就实现了。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5,inf = 1e9;
struct vwc{
int v,c;
vwc(int nv = inf,int nc = 0){
v = nv,c = nc;
}
bool emp(){
return v == inf;
}
};
struct node{
static node* gm,* tot;
node *lc = gm,*rc = gm;
vwc mn,lx,rn,mx;
int sz;
node* New(vwc ad){
mx = ad;
sz= ad.c;
// mx 一定非空，所以下文代码判断在左儿子还是右儿子靠得是mx
return this;
}
void del(int v){
sz--;
if ((v == mx.v) && mx.c){
mx.c--;
return;
}
if ((v == mn.v) && mn.c){
mn.c--;
return;
}
if ((v == lx.v) && lx.c){
lx.c--;
return;
}
if ((v == rn.v) && rn.c){
rn.c--;
return;
}
if ((lc == gm) || (v > lc->mx.v)){
rc->del(v);
}
else{
lc->del(v);
}
}
void ins(int l,int r,vwc ad){
sz += ad.c;
if (ad.v == mx.v){
mx.c += ad.c;
return;
}
if (ad.v == mn.v){
mn.c += ad.c;
return;
}
if (ad.v == lx.v){
lx.c += ad.c;
return;
}
if (ad.v == rn.v){
rn.c += ad.c;
return;
}
int mid = (l + r) >> 1;
if ((ad.v > mx.v) || (mx.emp())){
swap(ad,mx);
}
if (ad.emp()){
return;
}
if ((ad.v < mn.v) || (mn.emp())){
swap(ad,mn);
}
if (ad.emp()){
return;
}
if ((ad.v <= mid) && ((ad.v > lx.v) || (lx.emp()))){
swap(ad,lx);
}
if (ad.emp()){
return;
}
if ((ad.v > mid) && ((ad.v < rn.v) || (rn.emp()))){
swap(ad,rn);
}
// 注意，这里只能这么写，否则会因奇怪的 bug 导致不是按照这个顺序
if (ad.emp()){
return;
}
if (ad.v <= mid){
if (lc == gm){
lc =(++tot)->New(ad);
return;
}
lc->ins(l,mid,ad);
}
else{
if (rc == gm){
rc = (++tot)->New(ad);
return;
}
rc->ins(mid + 1,r,ad);
}
}
int kth(int k){
// <k 的个数
if (this == gm){
return 0;
}
if (mx.v < k){
return sz;
}
int ans = 0;
(mn.v < k) && (ans += mn.c);
(lx.v < k) && (ans += lx.c);
(rn.v < k) && (ans += rn.c);
if ((lc == gm) || (k > lc->mx.v)){
return rc->kth(k) + lc->sz + ans;
}
return lc->kth(k) + ans;
}
int nkth(int k){
// 第k个
//cout << mn.c << " " << mn.v << "\n";
if (k <= mn.c){
return mn.v;
}
k -= mn.c;
// cout << lc->sz << " " << lc->mx.v << "\n";
if (k <= lc->sz){
return lc->nkth(k);
}
k -= lc->sz;
//cout << lx.c << " " << lx.v << "\n";
if (k <= lx.c){
return lx.v;
}
k -= lx.c;
if (k <= rn.c){
return rn.v;
}
//cout << rn.c << " " << rn.v << "\n";
k -= rn.c;
//cout << rc->sz << " " << rc->mx.v << "\n";
if (k <= rc->sz){
return rc->nkth(k);
}
k -= rc->sz;
//cout << mx.c << " " << mx.v << "\n";
return mx.v;
}
int pre(int v){
return nkth(kth(v));
}
int nxt(int v){
return nkth(kth(v + 1) + 1);
}
}t[N];
node* node::gm = t,*node::tot = t,*rt = t;
int n;
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> n;
for (int i = 1,op,x;i <= n;i++){
cin >> op >> x;
if (op == 1){
if (rt == t){
rt = (++node::tot)->New(vwc{x,1});
continue;
}
rt->ins(-inf,inf,vwc{x,1});
}
else if (op == 2){
rt->del(x);
}
else if (op == 3){
cout << rt->kth(x) + 1 << "\n";
}
else if (op == 4){
cout << rt->nkth(x) << "\n";
}
else if (op == 5){
cout << rt->pre(x) << "\n";
}
else if (op == 6){
cout << rt->nxt(x) << "\n";
}
}
}