Treap 版本：
//OJ 1999
//by Cydiater
//2016.8.30
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
const int MAXN=1e5+5;
const int oo=0x3f3f3f3f;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,op,num,root=0,tol=0,ans=0;
struct node{
int leftt,rightt,v,cnt,rnd,siz;
}t[MAXN];
namespace solution{
void updata(int k){
t[k].siz=t[t[k].leftt].siz+t[t[k].rightt].siz+t[k].cnt;
}
void lefturn(int &k){
int tt=t[k].rightt;t[k].rightt=t[tt].leftt;t[tt].leftt=k;
t[tt].siz=t[k].siz;updata(k);k=tt;
}
void righturn(int &k){
int tt=t[k].leftt;t[k].leftt=t[tt].rightt;t[tt].rightt=k;
t[tt].siz=t[k].siz;updata(k);k=tt;
}
void insert(int &k,int x){
if(k==0){
tol++;k=tol;t[k].siz=t[k].cnt=1;
t[k].v=x;t[k].rnd=rand();
return;
}
t[k].siz++;
if(t[k].v==x) t[k].cnt++;
else if(x>t[k].v){
insert(t[k].rightt,x);
if(t[t[k].rightt].rnd<t[k].rnd)lefturn(k);
}else{
insert(t[k].leftt,x);
if(t[t[k].leftt].rnd<t[k].rnd)righturn(k);
}
}
void del(int &k,int x){
if(k==0) return;
if(t[k].v==x){
if(t[k].cnt>1){t[k].cnt--;t[k].siz--;return;}
if(t[k].leftt*t[k].rightt==0)k=t[k].leftt+t[k].rightt;
else if(t[t[k].leftt].rnd<t[t[k].rightt].rnd){
righturn(k);del(k,x);
}else{
lefturn(k);del(k,x);
}
}else if(x>t[k].v){
t[k].siz--;
del(t[k].rightt,x);
}else{
t[k].siz--;
del(t[k].leftt,x);
}
}
int query_rank(int k,int x){
if(k==0)return 0;
if(t[k].v==x) return t[t[k].leftt].siz+1;
else if(x>t[k].v) return t[t[k].leftt].siz+t[k].cnt+query_rank(t[k].rightt,x);
else return query_rank(t[k].leftt,x);
}
int query_num(int k,int x){
if(k==0) return 0;
if(x<=t[t[k].leftt].siz) return query_num(t[k].leftt,x);
else if(x>t[t[k].leftt].siz+t[k].cnt) return query_num(t[k].rightt,x-(t[t[k].leftt].siz+t[k].cnt));
else return t[k].v;
}
void query_pre(int k,int x){
if(k==0) return;
if(t[k].v<x){
ans=t[k].v;
query_pre(t[k].rightt,x);
}else query_pre(t[k].leftt,x);
}
void query_nxt(int k,int x){
if(k==0) return;
if(t[k].v>x){
ans=t[k].v;
query_nxt(t[k].leftt,x);
}else query_nxt(t[k].rightt,x);
}
void slove(){
N=read();
up(i,1,N){
op=read();num=read();
if(op==1)insert(root,num);
if(op==2)del(root,num);
if(op==3)printf("%d\n",query_rank(root,num));
if(op==4)printf("%d\n",query_num(root,num));
if(op==5){
query_pre(root,num);
printf("%d\n",ans);
}
if(op==6){
query_nxt(root,num);
printf("%d\n",ans);
}
}
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
slove();
return 0;
}
Splay 版本：
//BZOJ 3224
//by Cydiater
//2016.9.3
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
const int MAXN=1e6+5;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int root=0,tol=0,N,op,num;
struct SplayTree{
int son[2],siz,cnt,fa,v;
}t[MAXN];
namespace solution{
inline int get(int x){return x==t[t[x].fa].son[1];}//get left or right son
inline void clear(int x){
t[x].son[0]=t[x].son[1]=t[x].cnt=t[x].v=t[x].fa=t[x].siz=0;
}//reset node after deleted
inline void updata(int x){//updata node after rotated
if(x){
t[x].siz=t[x].cnt;
if(t[x].son[0])t[x].siz+=t[t[x].son[0]].siz;
if(t[x].son[1])t[x].siz+=t[t[x].son[1]].siz;
}
}
inline void rotate(int x){//rotate now node to root
int old=t[x].fa,oldf=t[old].fa,which=get(x);
t[old].son[which]=t[x].son[which^1];t[t[old].son[which]].fa=old;
t[old].fa=x;t[x].son[which^1]=old;
t[x].fa=oldf;
if(oldf)t[oldf].son[t[oldf].son[1]==old]=x;
updata(old);updata(x);
}
inline void splay(int x){
for(int fa;(fa=t[x].fa);rotate(x))if(t[fa].fa)
rotate((get(x)==get(fa)?fa:x));root=x;
}
inline void insert(int v){
if(root==0){
root=++tol;
t[root].son[0]=t[root].son[1]=t[root].fa=0;
t[root].v=v;t[root].cnt=t[root].siz=1;
return;
}
int now=root,fa=0;
while(1){
if(t[now].v==v){
t[now].cnt++;updata(now);updata(fa);
splay(now);break;
}
fa=now;now=t[now].son[t[now].v<v];
if(now==0){
now=++tol;
t[now].son[0]=t[now].son[1]=0;t[now].v=v;
t[now].siz=t[now].cnt=1;t[now].fa=fa;
t[fa].son[t[fa].v<v]=tol;
updata(fa);
splay(now);
break;
}
}
}
inline int find(int v){
int ans=0,now=root;
while(1){
if(v<t[now].v)now=t[now].son[0];
else{
ans+=(t[now].son[0]?t[t[now].son[0]].siz:0);
if(v==t[now].v){splay(now);return ans+1;}
ans+=t[now].cnt;
now=t[now].son[1];
}
}
}
inline int get_rank(int x){
int now=root;
while(1){
if(t[now].son[0]&&x<=t[t[now].son[0]].siz)now=t[now].son[0];
else{
int tmp=(t[now].son[0]?t[t[now].son[0]].siz:0)+t[now].cnt;
if(x<=tmp) return t[now].v;
x-=tmp;now=t[now].son[1];
}
}
}
inline int pre(){
int now=t[root].son[0];
while(t[now].son[1])now=t[now].son[1];
return now;
}
inline int nxt(){
int now=t[root].son[1];
while(t[now].son[0])now=t[now].son[0];
return now;
}
inline void del(int x){
int whatever=find(x);
if(t[root].cnt>1){
t[root].cnt--;
t[root].siz--;
return;
}
if(t[root].son[0]+t[root].son[1]==0){
clear(root);root=0;
return;
}
if(!t[root].son[0]){
int oldroot=root;root=t[root].son[1];t[root].fa=0;
clear(oldroot);return;
}else if(!t[root].son[1]){
int oldroot=root;root=t[root].son[0];t[root].fa=0;
clear(oldroot);return;
}
int leftbig=pre(),oldroot=root;
splay(leftbig);
t[t[oldroot].son[1]].fa=root;
t[root].son[1]=t[oldroot].son[1];
clear(oldroot);
updata(root);
return;
}
void debug(int now){
printf("now=%d t[now].son[0]=%d t[now].son[1]=%d t[now].siz=%d t[now].cnt=%d t[now].fa=%d t[now].v=%d\n",now,t[now].son[0],t[now].son[1],t[now].siz,t[now].cnt,t[now].fa,t[now].v);
if(t[now].son[0])debug(t[now].son[0]);
if(t[now].son[1])debug(t[now].son[1]);
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
N=read();
while(N--){
op=read();num=read();
if(op==1)insert(num);
if(op==2)del(num);
if(op==3)printf("%d\n",find(num));
if(op==4)printf("%d\n",get_rank(num));
if(op==5){
insert(num);printf("%d\n",t[pre()].v);del(num);
}
if(op==6){
insert(num);printf("%d\n",t[nxt()].v);del(num);
}
//debug(root);
//puts("");
}
return 0;
}
关于Splay写的很好的一个博客：