记录编号	432119	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	hunter	是否通过	通过
代码语言	C++	运行时间	0.734 s
提交时间	2017-08-02 20:47:46	内存使用	7.94 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn  1000005
const int INF=1<<30;
using namespace std;
struct node
{
     int sz,v;
     node *fa,*ch[2];
     node(int v=0):v(v){sz=1;fa=ch[0]=ch[1]=NULL;}
     inline int cmp(int x) { return x==v ? -1 : x>v ; }
     inline void up(){
        sz=1;
        if(ch[0]!=NULL) sz+=ch[0]->sz;
        if(ch[1]!=NULL) sz+=ch[1]->sz;
     }
}*nod[maxn*2];
int top=0,n;
inline void init(){
   for(int i=0;i<maxn;i++) nod[i]=new node();
}
inline void del(node* &p) {nod[--top]=p;p=NULL;}
inline void newnode(node* &p,int v,node* fa)
{
     p=nod[top++];
     *p=node(v);
     p->fa=fa;
}
node *root; 
struct splaytree
{
      inline int pd(node* p){return p->fa->ch[1]==p;}
      void rotate(node *p)
      {
           int c=pd(p)^1;
           node *t=p->fa;
           t->ch[c^1]=p->ch[c];
           if(p->ch[c]) p->ch[c]->fa=t;
           if((p->fa=t->fa)!=NULL) p->fa->ch[p->fa->ch[1]==t]=p;
           t->fa=p;
           p->ch[c]=t;
           t->up();
           p->up();
           if(p->fa==NULL) root=p;
      }
      void splay(node* p,node* target)
      {
          for(;p->fa!=target;rotate(p))
            if(p->fa->fa!=target) rotate(pd(p)==pd(p->fa)?p->fa:p);
      }
      void insert(node* p,int val)
      {
           if(root==NULL){newnode(root,val,NULL);return ;}
           node *fa=NULL;
           while(p!=NULL){
               fa=p;
               p=p->ch[val>p->v];               
           }
           newnode(p,val,fa);
           fa->ch[val>fa->v]=p;
           for(fa=p->fa;fa!=NULL;fa=fa->fa) fa->up();
           splay(p,NULL);
      }
      node* find(node* p,int val)
      {
            while(p!=NULL){
                int tmp=p->cmp(val);
                if(tmp==-1) return p;
                p=p->ch[tmp];
            }
            return NULL;
      }
      node* Max(node* p){
         if(p==NULL) return NULL;
         while(p->ch[1]!=NULL) p=p->ch[1];
         return p;
      }
      node* merge(node* a,node* b)
      {
            if(!b) return a;
            if(!a) return b;
            node *t=Max(a);
            splay(t,NULL);
            t->ch[1]=b;
            b->fa=t;
            t->up();
            return t; 
      }
      void remove(node* p,int val)
      {
          node* pos=find(root,val);
          splay(pos,NULL);
          pos=root;
          del(root);
          root=merge(pos->ch[0],pos->ch[1]);
          if(root!=NULL) root->fa=NULL;
      }
      int rank(node* p,int val)
      {
          int ret=1;
          while(p!=NULL){
             int tmp=val>p->v,d=p->ch[0]?p->ch[0]->sz:0;
             if(tmp) ret+=d+1;
             p=p->ch[tmp];
          }
          return ret;
      }
      int kth(node* p,int k)
      {
          while(p!=NULL){
             int d=p->ch[0]?p->ch[0]->sz:0;
             if(k==d+1) return p->v;
             if(k<d+1) p=p->ch[0];
             else{
                k-=d+1;
                p=p->ch[1];
             }
          }
          return -1;
      }
      int Pre(node* p,int val)
      {
          int ret=-INF;
          while(p!=NULL){
             int tmp=val> p->v;
             if(tmp) ret=max(ret,p->v);
             p=p->ch[tmp];
          }
          return ret;
      }
      int Sub(node *p,int val)
      {
          int ret=INF;
          while(p!=NULL){
             int tmp=val< p->v;
             if(tmp) ret=min(ret,p->v);
             p=p->ch[tmp^1];
          }
          return ret;
      }
}sp;
char s[25];
int main()
{
    freopen("phs.in","r",stdin);
    freopen("phs.out","w",stdout);
    int op,x;
    int n;
    scanf("%d",&n);init();
    while(n--){
        scanf("%d%d",&op,&x);
        if(op==1) sp.insert(root,x);
        if(op==2) sp.remove(root,x);
        if(op==3) printf("%d\n",sp.rank(root,x));
        if(op==4) printf("%d\n",sp.kth(root,x));
        if(op==5) printf("%d\n",sp.Pre(root,x));
        if(op==6) printf("%d\n",sp.Sub(root,x)); 
    }
    //while(1);
    return 0;
}