#5#6#7#8WA了,目前没有找到bug
用的treap,代码如下(码风见谅):
#include <bits/stdc++.h>
using namespace std;
int n,root=0,tot=0;
struct node{
int key,val,cnt,siz,l,r;
}tr[1000005];
void update(int u){
tr[u].siz=tr[tr[u].l].siz+tr[tr[u].r].siz+tr[u].cnt;
}
int newnode(int x){
tr[++tot].cnt=1;
tr[tot].key=x;
tr[tot].val=rand();
tr[tot].siz=1;
tr[tot].l=tr[tot].r=0;
return tot;
}
void lt(int &u){
int p=tr[u].r;
tr[u].r=tr[p].l;
tr[p].l=u;
tr[p].siz=tr[u].siz;
update(u);
u=p;
}
void rt(int &u){
int p=tr[u].l;
tr[u].l=tr[p].r;
tr[p].r=u;
tr[p].siz=tr[u].siz;
update(u);
u=p;
}
void insert(int &u,int x){
if(!u){
u=newnode(x);
return ;
}else{
tr[u].siz++;
}
if(tr[u].key==x){
tr[u].cnt++;
return ;
}
if(tr[u].key<x){
insert(tr[u].r,x);
if(tr[u].val>tr[tr[u].r].val)lt(u);
}else{
insert(tr[u].l,x);
if(tr[u].val>tr[tr[u].l].val)rt(u);
}
}
void del(int &u,int x){
if(tr[u].key==x){
if(tr[u].cnt>1){
tr[u].cnt--;
return ;
}
if(!tr[u].l||!tr[u].r){
u=tr[u].l+tr[u].r;
return ;
}
if(tr[tr[u].l].val<tr[tr[u].r].val){
lt(u);
del(u,x);
}else{
rt(u);
del(u,x);
}
return ;
}
tr[u].siz--;
if(tr[u].key<x){
del(tr[u].r,x);
}else{
del(tr[u].l,x);
}
return ;
}
int torank(const int x){
int u=root,res=0;
while(u){
// cout<<"!"<<u<<"!"<<tr[u].l<<"!"<<tr[u].r<<"!"<<tr[u].key<<endl;
if(tr[u].key==x)return res+tr[tr[u].l].siz+1;
if(x<tr[u].key)u=tr[u].l;
else res+=tr[tr[u].l].siz+tr[u].cnt,u=tr[u].r;
}
}
int tonum(int x){
int u=root;
while(u){
if(tr[tr[u].l].siz<x&&x<=tr[tr[u].l].siz+tr[u].cnt)return tr[u].key;
if(x<=tr[tr[u].l].siz)u=tr[u].l;
else x-=tr[u].cnt+tr[tr[u].l].siz,u=tr[u].r;
}
return 0;
}
int topre(int x){
int u=root,res=0;
while(u){
if(tr[u].key<x)res=tr[u].key,u=tr[u].r;
else u=tr[u].l;
}
return res;
}
int tonxt(int x){
int u=root,res=0;
while(u){
if(tr[u].key>x)res=tr[u].key,u=tr[u].l;
else u=tr[u].r;
}
return res;
}
void pmid(int u){
if(!u)return ;
pmid(tr[u].l);
cout<<tr[u].key<<' ';
pmid(tr[u].r);
}
int main() {
scanf("%d",&n);
while(n--){
int x,y;
scanf("%d%d",&x,&y);
switch(x){
case 1:{
insert(root,y);
break;
}
case 2:{
del(root,y);
break;
}
case 3:{
printf("%d\n",torank(y));
break;
}
case 4:{
printf("%d\n",tonum(y));
break;
}
case 5:{
printf("%d\n",topre(y));
break;
}
case 6:{
printf("%d\n",tonxt(y));
break;
}
}
/*
pmid(root);
cout<<endl;
cout<<endl;
*/
}
return 0;
}