如题，就是各种平衡树。
FHQ Treap
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0;bool f=false;char ch=getchar();
while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return f?-x:x;
}
mt19937 zsh(20070610);
struct Poi{
int key,val;
int siz;
int lson,rson;
}s[100010];
int cnt,rt;
void update(int pos)
{
s[pos].siz=s[s[pos].lson].siz+s[s[pos].rson].siz+1;
return;
}
int get_new_point(int k)
{
s[++cnt].key=k;
s[cnt].val=zsh();
s[cnt].siz=1;
return cnt;
}
void split(int pos,int k,int &p1,int &p2)
{
if(!pos) return p1=p2=0,void();
if(s[pos].key<=k) p1=pos,split(s[pos].rson,k,s[pos].rson,p2);
else p2=pos,split(s[pos].lson,k,p1,s[pos].lson);
update(pos);
return;
}
int merge(int p1,int p2)
{
if(p1&&p2)
{
if(s[p1].val>s[p2].val) return s[p1].rson=merge(s[p1].rson,p2),update(p1),p1;
else return s[p2].lson=merge(p1,s[p2].lson),update(p2),p2;
}
else return p1+p2;
}
void insert(int k)
{
int x=0,y=0,z=get_new_point(k);
split(rt,k,x,y);
x=merge(x,z);
rt=merge(x,y);
return;
}
void dele(int k)
{
int x=0,y=0,z=0;
split(rt,k-1,x,y);
split(y,k,y,z);
y=merge(s[y].lson,s[y].rson);
x=merge(x,y);
rt=merge(x,z);
return;
}
int get_x(int num)
{
int x=0,y=0;
split(rt,num-1,x,y);
int ret=s[x].siz;
rt=merge(x,y);
return ret;
}
int get_kth(int x)
{
int cur=rt;
while(cur)
{
if(s[s[cur].lson].siz>=x) cur=s[cur].lson;
else
{
x-=s[s[cur].lson].siz+1;
if(x==0) return s[cur].key;
else cur=s[cur].rson;
}
}
return -1;
}
int pre_num(int k)
{
int x=0,y=0;
split(rt,k-1,x,y);
int ret=x;
while(s[ret].rson) ret=s[ret].rson;
rt=merge(x,y);
return s[ret].key;
}
int nxt_num(int k)
{
int x=0,y=0;
split(rt,k,x,y);
int ret=y;
while(s[ret].lson) ret=s[ret].lson;
rt=merge(x,y);
return s[ret].key;
}
int n,op,x;
int main()
{
get_new_point(-100000000);
get_new_point(100000000);
rt=merge(1,2);
n=Qread();
while(n--)
{
op=Qread(),x=Qread();
if(op==1) insert(x);
else if(op==2) dele(x);
else if(op==3) printf("%d\n",get_x(x));
else if(op==4) printf("%d\n",get_kth(x+1));
else if(op==5) printf("%d\n",pre_num(x));
else printf("%d\n",nxt_num(x));
}
return 0;
}
Splay
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
struct czs{
int fa,son[2],num,wei,siz;
}s[100010];
int cnt,rt;
void output(int pos)
{
if(!pos) return;
output(s[pos].son[0]);
printf("%d ",s[pos].num);
output(s[pos].son[1]);
if(pos==rt) printf("\n");
}
void update(int pos)
{
return s[pos].siz=s[s[pos].son[0]].siz+s[s[pos].son[1]].siz+s[pos].wei,void();
}
bool be_lson(int pos)
{
return (pos==s[s[pos].fa].son[0]);
}
void rotate(int pos)
{
int y=s[pos].fa,chk=be_lson(pos),z=s[s[pos].fa].fa;
if(z) s[z].son[be_lson(y)^1]=pos;
s[pos].fa=z;
s[y].son[chk^1]=s[pos].son[chk];
s[s[pos].son[chk]].fa=y;
s[pos].son[chk]=y;
s[y].fa=pos;
update(y),update(pos);
return;
}
void Splay(int pos,int rrt)
{
for(int k=s[pos].fa;k=s[pos].fa,k!=rrt;rotate(pos))
if(s[k].fa!=rrt) rotate(be_lson(k)==be_lson(pos)?k:pos);
if(!rrt) rt=pos;
}
void insert_num(int k)
{
if(!rt)
{
s[++cnt].num=k;
s[cnt].wei++;
return update(rt=cnt);
}
int cur=rt,f=0;
while(1)
{
if(s[cur].num==k)
{
s[cur].wei++;
update(cur),update(f);
Splay(cur,0);
break;
}
f=cur;
cur=s[cur].son[s[cur].num<k];
if(!cur)
{
s[++cnt].num=k;
s[cnt].wei++;s[cnt].fa=f;
s[f].son[s[f].num<k]=cnt;
update(cnt);update(f);
Splay(cnt,0);
break;
}
}
return;
}
int get_rk(int k)
{
int cur=rt;
if(!rt) return 0;
while(s[cur].son[k>s[cur].num]&&k!=s[cur].num)
cur=s[cur].son[k>s[cur].num];
return Splay(cur,0),s[s[cur].son[0]].siz+1;
}
int get_kth(int k)
{
int cur=rt;
while(1)
{
if(s[cur].son[0]&&k<=s[s[cur].son[0]].siz) cur=s[cur].son[0];
else
{
k-=s[s[cur].son[0]].siz+s[cur].wei;
if(k<=0) return Splay(cur,0),s[cur].num;
cur=s[cur].son[1];
}
}
}
int next_num(int k,int fr)
{
get_rk(k);
int cur=rt;
if(s[cur].num>k&&fr) return cur;
if(s[cur].num<k&&!fr) return cur;
cur=s[cur].son[fr];
while(s[cur].son[fr^1]) cur=s[cur].son[fr^1];
Splay(cur,0);
return cur;
}
void delete_num(int k)
{
int fro=next_num(k,0),aft=next_num(k,1);
Splay(fro,0);Splay(aft,fro);
int del=s[aft].son[0];
if(s[del].wei>1) return s[del].wei--,Splay(del,0);
else s[aft].son[0]=0;
}
int n,op,x;
int main()
{
n=Qread();
insert_num(10000010);
insert_num(-10000010);
while(n--)
{
op=Qread();x=Qread();
if(op==1) insert_num(x);
else if(op==2) delete_num(x);
else if(op==3) printf("%d\n",get_rk(x)-1);
else if(op==4) printf("%d\n",get_kth(x+1));
else if(op==5) printf("%d\n",s[next_num(x,0)].num);
else printf("%d\n",s[next_num(x,1)].num);
}
return 0;
}