Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 12015 Solved: 5136
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.每个数的数据范围：[-2e9,2e9]
Source
替罪羊树
曾经我一直以为替罪羊树就是不平衡的时候拍扁了重建……
真是拿衣服
从yhx那里get了神奇的删点方法：找到它的前驱pre，用pre代替它←虽然只有一句话，但这是整道题最麻烦的地方
http://blog.csdn.net/sdfzyhx/article/details/70212142
代码里同时用到了st,top,st2,top2两组变量，写的时候我还在想这样会不会写混，事实证明果然写混调了半天……
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct node{
int l,r;
int val,sz;
int cnt;
bool operator < (const node b)const{
return val<b.val;
}
}t[mxn],vt[mxn];
int rot=;
int sz=,cnt=;
int st[mxn],top=;
int flag=,faf;
int newnode(){
int res=;
if(top)res=st[top--];
else res=++cnt;
t[res].sz=t[res].l=t[res].r=t[res].cnt=;
return res;
}
void pushup(int x){
t[x].sz=t[t[x].l].sz+t[t[x].r].sz+t[x].cnt;return;
}
void Build(int l,int r,int &rt){
if(l>r){rt=;return;}
int mid=(l+r)>>;
rt=newnode();
t[rt].val=vt[mid].val;
t[rt].cnt=vt[mid].cnt;
t[rt].sz=t[rt].cnt;
Build(l,mid-,t[rt].l);
Build(mid+,r,t[rt].r);
pushup(rt);
return;
}
void insert(int &rt,int x){
if(!rt){
rt=newnode();
t[rt].val=x;
t[rt].cnt=t[rt].sz=;
return;
}
t[rt].sz++;
if(t[rt].val==x){
t[rt].cnt++;
return;
}
if(x<t[rt].val)insert(t[rt].l,x);
else insert(t[rt].r,x);
if(t[t[rt].l].sz/(double)t[rt].sz>0.666)flag=rt;
if(flag==t[rt].l || flag==t[rt].r)faf=rt;
pushup(rt);
return;
}
void del(int rt){
if(!rt)return;
vt[++sz]=t[rt];
st[++top]=rt;
del(t[rt].l);
del(t[rt].r);
return;
}
int pre(int rt,int x){
int res=-2e9-,pos=;
while(rt){
if(t[rt].val>=x){
rt=t[rt].l;
}
else{
if(t[rt].val>res){res=t[rt].val;pos=rt;}
rt=t[rt].r;
}
}
return pos;
}
int sub(int rt,int x){
int res=2e9+,pos=;
while(rt){
if(t[rt].val<=x){
rt=t[rt].r;
}
else{
if(t[rt].val<res){res=t[rt].val;pos=rt;}
rt=t[rt].l;
}
}
return pos;
}
int st2[mxn],top2=,fafa;
void Q_erase(int &rt,int x){
// if(!rt && x==299181)while(1);
if(t[rt].val==x){
t[rt].cnt--;
t[rt].sz--;
if(!t[rt].cnt){
if(t[rt].l*t[rt].r==){rt=t[rt].l+t[rt].r;return;}
int p=t[rt].l;
while(t[p].r){st2[++top2]=p;p=t[p].r;}
if(top2){
t[st2[top2]].r=t[p].l;
pushup(st2[top2]);
t[p].l=t[rt].l;
t[p].r=t[rt].r;
while(top2)pushup(st2[top2--]);
}
else t[p].r=t[rt].r;
if(fafa){
if(t[fafa].l==rt) t[fafa].l=p;
else t[fafa].r=p;
}
pushup(p);
pushup(t[rt].l);
rt=p;
}
pushup(fafa);
return;
}
fafa=rt;
if(x<t[rt].val)Q_erase(t[rt].l,x);
else Q_erase(t[rt].r,x);
pushup(rt);
return;
}
int Q_rank(int rt,int x){
int res=;
while(rt){
if(t[rt].val<x){
res+=t[t[rt].l].sz+t[rt].cnt;
rt=t[rt].r;
}
else rt=t[rt].l;
}
return res+;
}
int Q_num(int rt,int k){
int res=;
while(rt){
if(t[t[rt].l].sz>=k){
res=t[rt].val;
rt=t[rt].l;
}
else if(t[t[rt].l].sz+t[rt].cnt>=k)return t[rt].val;
else k-=t[t[rt].l].sz+t[rt].cnt,rt=t[rt].r;
}
return res;
}
void Debug(int x){
if(!x)return;
printf("#%d: v:%d l:%d r:%d sz:%d cnt:%d\n",
x,t[x].val,t[x].l,t[x].r,t[x].sz,t[x].cnt);
Debug(t[x].l);Debug(t[x].r);
}
int n;
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.out","w",stdout);
int i,j;
n=read();
int op,x;
int tct=;
while(n--){
op=read();x=read();
if(op!=)tct++;
switch(op){
case :{
flag=faf=;sz=;
insert(rot,x);
if(flag){
del(flag);
sort(vt+,vt+sz+);
if(flag==rot)Build(,sz,rot);
else Build(,sz,(t[faf].l==flag)?t[faf].l:t[faf].r);
}
break;
}
case :{fafa=;Q_erase(rot,x);break;}
case :{
int ans=Q_rank(rot,x);
printf("%d\n",ans);
break;
}
case :{
int ans=Q_num(rot,x);
printf("%d\n",ans);
break;
}
case :{
int res=pre(rot,x);
printf("%d\n",t[res].val);
break;
}
case :{
int res=sub(rot,x);
printf("%d\n",t[res].val);
break;
}
case :{
Debug(rot);
break;
}
}
}
return ;
}