您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
插入x数
删除x数(若有多个相同的数，因只删除一个)
查询x数的排名(若有多个相同的数，因输出最小的排名)
查询排名为x的数
求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
--by 洛谷；
http://www.lydsy.com/JudgeOnline/problem.php?id=3224
话说，没时间写题解啊——
不过，也就是个平衡树的模板题；
就存下代码吧
treap哟；
好像很少见写treap的，但常数还是挺小的orz；
哎，最近怎么老写模板啊？
代码如下：
#include<cstdio>
#include<cstdlib>
using namespace std;
#define INF 2147483647
int n;
struct poo
{
int size,value,key,cnt;
int ch[];
}data[];
int tot,root,x;
int make_data(int );
void insert(int&);
void roll(int&);
int find( );
int rank( );
void del(int&);
int las(int );
int nex(int );
void up(int );
int main()
{
int i,j;
data[].value=INF;data[].key=INF;
scanf("%d",&n);
for(i=;i<=n;i++){
scanf("%d%d",&j,&x);
switch(j){
case :insert(root);break;
case : del(root);break;
case : printf("%d\n",rank( ));break;
case : printf("%d\n",find( ));break;
case : printf("%d\n", las(root));break;
case : printf("%d\n", nex(root));break;
}
}
}
int make_data(int value)
{
tot++;
data[tot].cnt++;
data[tot].key=(rand()/+rand()/);
data[tot].size=;
data[tot].value=value;
return tot;
}
void insert(int &now)
{
if(now==){
now=make_data(x);
return;
}
if(data[now].value==x){
data[now].cnt++;
data[now].size++;
}
else{
int wh=x < data[now].value ? : ;
insert(data[now].ch[wh]);
if(data[now].key>=data[data[now].ch[wh]].key)
roll(now);
}
up(now);
}
void roll(int &now)
{
int wh=data[data[now].ch[]].key<data[data[now].ch[]].key?:;
int son=data[now].ch[wh];
data[now].ch[wh]=data[son].ch[wh^];
data[son].ch[wh^]=now;
up(now);
now=son;
}
int find()
{
int now=root;
int ls,rs;
ls=data[now].ch[];rs=data[now].ch[];
while(x<=data[ls].size||x>data[now].size-data[rs].size){
if(data[ls].size>=x)
now=ls;
else{
x=x+data[rs].size-data[now].size;
now=rs;
}
ls=data[now].ch[];rs=data[now].ch[];
}
return data[now].value;
}
int rank()
{
int now=root,ans=;
int ls=data[now].ch[],rs=data[now].ch[];
while(x!=data[now].value&&x!=)
{
if(x<data[now].value)
now=ls;
else{
ans+=data[now].size-data[rs].size;
now=rs;
}
ls=data[now].ch[];rs=data[now].ch[];
}
return ans+data[ls].size+;
}
void del(int &now)
{
if(data[now].value==x){
if(data[now].cnt==){
if(data[now].ch[]*data[now].ch[]==){
now=data[now].ch[]+data[now].ch[];
return ;
}
roll(now);
int wh=data[data[now].ch[]].value==x?:;
del(data[now].ch[wh]);
}
else{
data[now].size--; data[now].cnt--;
}
}
else{
int wh=data[now].value>x?:;
del(data[now].ch[wh]);
}
up(now);
}
int las(int now)
{
int ans=,an=;
if(!now)return ;
if(data[now].value<x){
ans=data[now].value;
an=las(data[now].ch[]);
ans=an!=?an:ans;
}
else{
ans=las(data[now].ch[]);
}
return ans;
}
int nex(int now)
{
int ans=,an=;
if(!now)return ;
if(data[now].value>x){
ans=data[now].value;
an=nex(data[now].ch[]);
ans=an!=?an:ans;
}
else{
ans=nex(data[now].ch[]);
}
return ans;
}
void up(int now)
{
data[now].size=data[data[now].ch[]].size+data[data[now].ch[]].size+data[now].cnt;
}
//treap on the 2017.1.21
//10
//1 5
//4 1
//1 6
//1 7
//1 10
//1 3
//1 4
//6 2
//1 8
//5 9
//
//14
//1 5
//1 6
//1 7
//1 10
//1 3
//1 4
//1 8
//3 3
//3 4
//3 5
//3 6
//4 5
//4 6
//4 7
祝AC哟；