用splay实现二叉搜索树的模板，支持插入，删除，找前缀后缀，x的排名以及第x名的数。
#include <cstdio>
#define l(x) t[x].s[0]
#define r(x) t[x].s[1]
#define f(x) t[x].p
#define lc(x) (r(f(x)) == x)
#define st(a,b,c) t[a].s[c] = b; f(b) = a const int N = ;
int m,x,op,tt,rt;
struct nd {int v,p,sz,s[];}t[N]; void pu(int x) {t[x].sz = t[l(x)].sz+t[r(x)].sz+;}
void rot(int x) {
int y = f(x), z = f(y), lx = lc(x), ly = lc(y);
st(y,t[x].s[!lx],lx); st(z,x,ly); st(x,y,!lx); pu(y);
}
void sp(int x) {
for(int y; y = f(x); rot(x)) if(f(y)) {
if(lc(x)^lc(y)) rot(x); else rot(y);
}
pu(x), rt = x;
}
void in(int x) {
int c = rt;
while(t[c].s[t[c].v<x]) t[c].sz++, c = t[c].s[t[c].v<x];
if(c) t[c].sz++; t[c].s[t[c].v<x] = ++tt, f(tt) = c, t[tt].v = x, t[tt].sz = , sp(tt);
}
void del(int x) {
int c = rt;
while() {
if(t[c].v == x) {x = c; break;}
if(t[c].v < x) c = r(c); else c = l(c);
}
sp(x);
if(!l(x)) f(r(x)) = , rt = r(x);
else if(!r(x)) f(l(x)) = , rt = l(x);
else {
f(l(x)) = , c = l(x);
while(r(c)) c = r(c);
sp(c), r(c) = r(x), f(r(x)) = c;
}
}
int pre(int x) {
int c = rt, ans = 0xcfcfcfcf;
while(c) if(t[c].v < x) ans = t[c].v, c = r(c); else c = l(c);
return ans;
}
int nxt(int x) {
int c = rt, ans = 0x3f3f3f3f;
while(c) if(t[c].v > x) ans = t[c].v, c = l(c); else c = r(c);
return ans;
}
int rk(int x) {
int c = rt, k = , ans = ;
while(c) if(t[c].v < x) ans = k+t[l(c)].sz+, k += t[l(c)].sz+, c = r(c); else c = l(c);
return ans+;
}
int sa(int x, int k) {
if(t[l(x)].sz == k-) return t[x].v;
if(t[l(x)].sz >= k) return sa(l(x), k);
return sa(r(x), k-t[l(x)].sz-);
} int main() {
scanf("%d", &m);
while(m--) {
scanf("%d%d", &op, &x);
if(op == ) in(x);
else if(op == ) del(x);
else if(op == ) printf("%d\n", rk(x));
else if(op == ) printf("%d\n", sa(rt,x));
else if(op == ) printf("%d\n", pre(x));
else printf("%d\n", nxt(x));
}
return ;
}