算法复习——splay(bzoj3224)

题目：

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

Sample Output

106465
84185
492737

HINT

1.n的数据范围：n<=100000

2.每个数的数据范围：[-2e9,2e9]

题解：

splay模板题···表示两周没碰键盘手都生了····

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int N=;

int root,size[N],son[N][],key[N],cnt[N],tot,father[N];

int a,b,n;

inline void clear(int now)

{

  size[now]=son[now][]=son[now][]=key[now]=cnt[now]=father[now]=;

}

inline void update(int now)

{

  if(now)

  {

    size[now]=cnt[now];

    if(son[now][])  size[now]+=size[son[now][]];

    if(son[now][])  size[now]+=size[son[now][]];

  }

}

inline int get(int a)

{

  return son[father[a]][]==a;

}

inline void rotate(int now)

{

  int fa=father[now],ofa=father[fa],which=get(now);

  son[fa][which]=son[now][which^],father[son[fa][which]]=fa;

  son[now][which^]=fa,father[fa]=now,father[now]=ofa;

  if(ofa)  son[ofa][son[ofa][]==fa]=now;

  update(fa),update(now);

}

inline void splay(int now)

{

  while(father[now])

  {

    if(father[father[now]])  rotate(get(now)==get(father[now])?father[now]:now);

    rotate(now);

  }

  root=now;

}

inline void insert(int x)

{

  int now=root,last=;

  while(true)

  {

    if(!now)

    {

      now=++tot;size[now]=cnt[now]=;father[now]=last;key[now]=x;

      son[last][key[now]>key[last]]=now;update(last);splay(now);

      break;

    }

    if(key[now]==x)

    {

      cnt[now]++;update(now);update(last);splay(now);

      break;

    }

    last=now;now=son[now][x>key[now]];

  }

}

inline int find(int x)

{

  int now=root,ans=;

  while(true)

  {

    if(x<key[now])  now=son[now][];

    else

    {

      ans+=size[son[now][]];

      if(x==key[now])  {splay(now);return ans+;}

      ans+=cnt[now];now=son[now][];

    }

  }

}

inline int findx(int x)

{

  int now=root;

  while(true)

  {

    if(x<=size[son[now][]])  now=son[now][];

    else

    {

      int temp=size[son[now][]]+cnt[now];

      if(x<=temp)  return key[now];

      x-=temp;now=son[now][];

    }

  }

}

inline int pre()

{

  int now=son[root][];

  while(son[now][])  now=son[now][];

  return now;

}

inline int next()

{

  int now=son[root][];

  while(son[now][])  now=son[now][];

  return now;

}

inline void Delete(int x)

{

  int nothing=find(x);

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

  else if(!son[root][]&&!son[root][])

  {clear(root);root=;return;}

  else if(!son[root][])

  {int oldroot=root;root=son[root][];father[root]=;clear(oldroot);return;}

  else if(!son[root][])

  {int oldroot=root;root=son[root][];father[root]=;clear(oldroot);return;}

  else

  {

    int leftbig=pre(),oldroot=root;

    splay(leftbig);son[root][]=son[oldroot][];

    father[son[root][]]=root;clear(oldroot);

    update(root);

    return;

  }

}

inline int findpre(int x)

{

  insert(x);int temp=pre();

  Delete(x);return key[temp];

}

inline int findnext(int x)

{

  insert(x);int temp=next();

  Delete(x);return key[temp];

}

int main()

{

  //freopen("a.in","r",stdin);

  scanf("%d",&n);

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

  {

    scanf("%d%d",&a,&b);

    if(a==)

      insert(b);

    if(a==)

      Delete(b);

    if(a==)

    {

      int temp=find(b);

      printf("%d\n",temp);

    }

    if(a==)

    {

      int temp=findx(b);

      printf("%d\n",temp);

    }

    if(a==)

    {

      int temp=findpre(b);

      printf("%d\n",temp);

    }

    if(a==)

    {

      int temp=findnext(b);

      printf("%d\n",temp);

    }

   }

  return ;

}

巴特西