[模板] Splay

欠了好久的Splay，以后就它了。

默写真不容易，过几天估计就忘了..

整个Splay真的精妙，不拖泥带水那种..

前驱后继之所以不能用rk转到根，是因为这个数不一定存在。。

kth中<=老忘记=

#include<iostream>

#include<cstdio>

#define check(x) (x==ch[fa[x]][1])

#define clear(x) val[x]=cnt[x]=siz[x]=ch[x][0]=ch[x][1]=fa[x]=0

#define pushup(x) siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x]

using namespace std;

const int MAXN=100005;

int val[MAXN],cnt[MAXN],siz[MAXN];

int ch[MAXN][2],fa[MAXN];

int tot,root;

inline int newnode(int x){cnt[++tot]++;siz[tot]=1;val[tot]=x;return tot;}

void rotate(int x){

  int y=fa[x],z=fa[fa[x]];

  bool ck=check(x);

  fa[ch[x][ck^1]]=y;ch[y][ck]=ch[x][ck^1];

  ch[x][ck^1]=y;fa[y]=x;fa[x]=z;

  if(z) ch[z][ch[z][1]==y]=x;

  pushup(y);pushup(x);

}

void splay(int x){

  for(int f=fa[x];f;rotate(x),f=fa[x])

    if(fa[f]) rotate(check(f)==check(x)?f:x);

  root=x;

}

void insert(int x){

  if(!root){root=newnode(x);return;}

  int cur=root,f=0;

  while(1){

    if(val[cur]==x){cnt[cur]++;pushup(cur);pushup(f);splay(cur);return;}

    f=cur;cur=ch[cur][x>val[cur]];

    if(!cur){cur=newnode(x);fa[cur]=f;ch[f][x>val[f]]=cur;pushup(f);splay(cur);return;}

  }

}

int rk(int x){

  int cur=root,ret=0;

  while(1){

    if(x<val[cur]) cur=ch[cur][0];

    else{

      ret+=siz[ch[cur][0]];

      if(val[cur]==x) return splay(cur),ret+1;//

      ret+=cnt[cur];cur=ch[cur][1];

    }

  }

}

int kth(int x){

  int cur=root;

  while(1){

    if(ch[cur][0]&&x<=siz[ch[cur][0]]) cur=ch[cur][0];

    else{

      x-=siz[ch[cur][0]]+cnt[cur];

      if(x<=0) return cur;

      cur=ch[cur][1];

    }

  }

}

int prev(){

  int cur=ch[root][0];

  while(ch[cur][1]) cur=ch[cur][1];

  return cur;

}

int nxtv(){

  int cur=ch[root][1];

  while(ch[cur][0]) cur=ch[cur][0];

  return cur;

}

void del(int x){

  rk(x);

  if(cnt[root]>1){cnt[root]--;pushup(root);return;}

  if(!ch[root][0]&&!ch[root][1]){clear(root);root=0;return;}

  if(!ch[root][0]){int sav=root;root=ch[sav][1];fa[root]=0;clear(sav);return;}

  if(!ch[root][1]){int sav=root;root=ch[sav][0];fa[root]=0;clear(sav);return;}

  int sav=root;

  splay(prev());

  ch[root][1]=ch[sav][1];

  fa[ch[sav][1]]=root;

  clear(sav);

  pushup(root);

}

int n;

inline int rd(){

  int ret=0,f=1;char c;

  while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;

  while(isdigit(c))ret=ret*10+c-'0',c=getchar();

  return ret*f;

}

int main(){

  n=rd();

  int x,y;

  for(int i=1;i<=n;i++){

    x=rd();y=rd();

    switch(x){

    case 1:{insert(y);break;}

    case 2:{del(y);break;}

    case 3:{printf("%d\n",rk(y));break;}

    case 4:{printf("%d\n",val[kth(y)]);break;}

    case 5:{insert(y);printf("%d\n",val[prev()]);del(y);break;}

    case 6:{insert(y);printf("%d\n",val[nxtv()]);del(y);break;}

    }

  }

  return 0;

}