Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-1e7,1e7]
Source
Splay模板题，膜了YveH爷的模板，不过代码好长，常数还很大。。。好歹是打粗来了
#include <cstdio>
using namespace std;
struct SplayNode
{
SplayNode *fa,*ch[];
SplayNode();
int data,num,size;
int chr() {return this==fa->ch[];}
void updata() { size=ch[]->size+ch[]->size+num;}
}*null;
SplayNode::SplayNode() {fa=ch[]=ch[]=null; size=; num=;}
int n;
namespace Splay
{
SplayNode *Root;
void MakeTree()
{
null=new SplayNode;
*null=SplayNode();
Root=null;
}
void rotate(SplayNode *x)
{
SplayNode *r=x->fa;
if (r==null || x==null) return;
int t=x->chr();
r->ch[t]=x->ch[t^];
r->ch[t]->fa=r;
if (r->fa==null) Root=x;
else r->fa->ch[r->chr()]=x;
x->fa=r->fa;
x->ch[t^]=r;
r->fa=x;
r->updata();
x->updata();
}
void splay(SplayNode *x,SplayNode *y)
{
for (;x->fa!=y;rotate(x))
if (x->fa->fa!=y)
if (x->chr()==x->fa->chr()) rotate(x->fa);
else rotate(x);
}
void insert(int v)
{
SplayNode *r=Root;
if (Root==null)
{
Root=new SplayNode;
Root->data=v;
Root->updata();
return;
}
if (Root->data==v)
{
Root->num++;
Root->updata();
return;
}
while (r->ch[r->data<v]!=null)
{
r=r->ch[r->data<v];
if (r->data==v)
{
r->num++;
splay(r,null);
return;
}
}
r->ch[r->data<v]=new SplayNode;
r->ch[r->data<v]->data=v;
r->ch[r->data<v]->fa=r;
splay(r->ch[r->data<v],null);
}
SplayNode *Kth(int k)
{
SplayNode *r=Root;
while (r!=null)
{
if (k<=r->ch[]->size) r=r->ch[];
else if (k>=r->ch[]->size+ && k<=r->ch[]->size+r->num) return r;
else
{
k=k-r->ch[]->size-r->num;
r=r->ch[];
}
}
return r;
}
SplayNode *find(int v)
{
SplayNode *r=Root;
while (r!=null)
{
if (r->data==v)
{
splay(r,null);
return r;
}
r=r->ch[r->data<v];
}
return null;
}
SplayNode *pre()
{
SplayNode *r=Root->ch[];
if (r==null) return null;
while (r->ch[]!=null) r=r->ch[];
return r;
}
SplayNode *suc()
{
SplayNode *r=Root->ch[];
if (r==null) return null;
while (r->ch[]!=null) r=r->ch[];
return r;
}
void del(int v)
{
find(v);
SplayNode *q=pre();
SplayNode *p=suc();
if (q==null && p==null)
if (Root->num==) Root=null;
else Root->num--,Root->updata();
if (q==null)
{
splay(p,null);
if (Root->ch[]->num==) Root->ch[]=null,Root->updata();
else Root->ch[]->num--,splay(Root->ch[],null);
return;
}
if (p==null)
{
splay(q,null);
if (Root->ch[]->num==) Root->ch[]=null,Root->updata();
else Root->ch[]->num--,splay(Root->ch[],null);
return;
}
splay(q,null);
splay(p,q);
if (p->ch[]->num==) p->ch[]=null,p->updata();
else p->ch[]->num--,splay(p->ch[],null);
return;
}
}
void solve()
{
int temp,x;
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%d%d",&temp,&x);
if (temp==) Splay::insert(x);
if (temp==) Splay::del(x);
if (temp==) printf("%d\n",Splay::find(x)->ch[]->size+);
if (temp==) printf("%d\n",Splay::Kth(x)->data);
if (temp==)
{
Splay::insert(x);
printf("%d\n",Splay::pre()->data);
Splay::del(x);
}
if (temp==)
{
Splay::insert(x);
printf("%d\n",Splay::suc()->data);
Splay::del(x);
}
}
}
int main()
{
Splay::MakeTree();
solve();
return ;
}