记录编号	364937	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.360 s
提交时间	2017-01-18 18:51:56	内存使用	5.63 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200000;
struct node{
  node *ch[2],*prt;
  int sz,Max,Min,data;
  node(){}
  node(int x,node *p=0){
    Max=Min=data=x;prt=p;sz=1;
    ch[0]=ch[1]=0;prt=p;
  }
  void update(){
    Max=Min=data;
    sz=1;
    if(ch[0])sz+=ch[0]->sz,Max=max(Max,ch[0]->Max),Min=min(Min,ch[0]->Min);
    if(ch[1])sz+=ch[1]->sz,Max=max(Max,ch[1]->Max),Min=min(Min,ch[1]->Min);
  }
}t[maxn];int tot=0;
node *newnode(int x,node *p=0){
  t[++tot]=node(x,p);return t+tot;
}
inline int isrch(node* rt){return rt==(rt->prt->ch[1]);}
node *root;
void rot(node* rt,int t){
  node *c=rt->ch[t],*p=rt->prt;
  if(!p)root=c;
  else p->ch[isrch(rt)]=c;
  c->prt=p;
  rt->ch[t]=c->ch[t^1];
  if(c->ch[t^1])c->ch[t^1]->prt=rt;
  c->ch[t^1]=rt;rt->prt=c;
  rt->update();c->update();
}
void splay(node* rt,node *ed){
  node *p,*g;
  while((p=rt->prt)&&(g=p->prt)){
    if(p==ed)return;
    else if(g==ed){
      rot(p,isrch(rt));return;
    }else{
      int t1=isrch(rt),t2=isrch(p);
      if(t1==t2){
	rot(g,t2);rot(p,t1);
      }else{
	rot(p,t1);rot(g,t2);
      }
    }
  }
  if(ed==0&&p!=0){
    rot(p,isrch(rt));
  }
}
void insert(node *rt,int x){
  if(!rt){
    root=newnode(x,0);return;
  }
  int t=(x>=rt->data);
  if(rt->ch[t])insert(rt->ch[t],x);
  else{
    splay(rt,0);
    node *c=rt->ch[t];
    root=newnode(x,0);
    root->ch[t^1]=rt;rt->prt=root;
    rt->ch[t]=0;if(c)c->prt=root;root->ch[t]=c;
    rt->update();root->update();
  }
}
node *search(node *rt,int x){
  if(x!=rt->data)return search(rt->ch[x>rt->data],x);
  if(rt->ch[0]&&rt->ch[0]->Max==x)return search(rt->ch[0],x);
  return rt;
}
void remove(node *rt,int x){
  if(x!=rt->data){
    remove(rt->ch[x>rt->data],x);
  }else{
    splay(rt,0);
    node *m=search(rt->ch[1],rt->ch[1]->Min);
    splay(m,rt);
    root=m;root->prt=0;
    m->ch[0]=rt->ch[0];rt->ch[0]->prt=root;
    root->update();
  }
}
int rk(int x){
  splay(search(root,x),0);
  return root->ch[0]->sz;
}
int kth(node *rt,int x){
  int lsz=(rt->ch[0])?(rt->ch[0]->sz):0;
  if(x<=lsz)return kth(rt->ch[0],x);
  if(x==lsz+1){splay(rt,0);return rt->data;}
  return kth(rt->ch[1],x-lsz-1);
}
int pred(node *rt,int x){
  if(rt->data>=x)return pred(rt->ch[0],x);
  if(rt->ch[1]&&rt->ch[1]->Min<x)return pred(rt->ch[1],x);
  return rt->data;
}
int succ(node *rt,int x){
  if(rt->data<=x)return succ(rt->ch[1],x);
  if(rt->ch[0]&&rt->ch[0]->Max>x)return succ(rt->ch[0],x);
  return rt->data;
  
}
int main(){
  freopen("phs.in","r",stdin);
  freopen("phs.out","w",stdout);
  insert(root,1000000000);insert(root,-1000000000);
  int n,t,x;
  scanf("%d",&n);
  for(int i=1;i<=n;++i){
    scanf("%d%d",&t,&x);
    if(t==1)insert(root,x);
    else if(t==2)remove(root,x);
    else if(t==3)printf("%d\n",rk(x));
    else if(t==4)printf("%d\n",kth(root,x+1));
    else if(t==5)printf("%d\n",pred(root,x));
    else printf("%d\n",succ(root,x));
  }
  fclose(stdin);fclose(stdout);
  return 0;
}