P3369 【模板】普通平衡树

上山打老虎

纯板子。。。。
题意：

插入 xx 数
删除 xx 数(若有多个相同的数，因只删除一个)
查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 。若有多个相同的数，因输出最小的排名)
查询排名为 xx 的数
求 xx 的前驱(前驱定义为小于 xx ，且最大的数)
求 xx 的后继(后继定义为大于 xx ，且最小的数)

然后。。。
然后就没有然后了。。。。
注意rotate。。。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cctype>
using namespace std;
#define olinr return 
#define love_nmr 0
#define INF 0x7ffffffa
#define mod 123123
int n;
int cnt;
int root;
int siz[mod];
int dat[mod];
int fat[mod];
int num[mod];
int son[mod][2];
inline int read()
{
  int f=1,x=0;
  char ch=getchar();
  while(!isdigit(ch))
  {
    if(ch=='-')
      f=-f;
    ch=getchar();
  }
  while(isdigit(ch))
  {
    x=(x<<1)+(x<<3)+(ch^48);
    ch=getchar();
  }
  olinr x*f;
}
inline void put(int x)
{
  if(x<0)
  {
    putchar('-');
    x=-x;
  }
  if(x>9)
    put(x/10);
  putchar(x%10+'0');
}

/* ------------------------olinr love nmr--------------------------------*/

inline void update(int x)
{
  siz[x]=siz[son[x][0]]+siz[son[x][1]]+num[x];
}
inline void rotate(int x,int &o)
{
  int y=fat[x];
  int z=fat[y];
  bool xx=son[y][1]==x;
  bool yy=xx^1;
  if(y==o)
    o=x;
  else
    son[z][son[z][1]==y]=x;
  fat[x]=z;
  fat[y]=x;
  fat[son[x][yy]]=y;
  son[y][xx]=son[x][yy];
  son[x][yy]=y;
  update(y);
  update(x);
  olinr;
}
inline void splay(int x,int &o)
{
  while(x!=o)
  {
    int y=fat[x];
    int z=fat[y];
    if(y!=o)
    {
      if((son[y][0]==x)^(son[z][0]==y))
        rotate(x,o);
      else
        rotate(y,o);
    }  
    rotate(x,o);
  }
}
inline int x_rank_n(int x)
{
  int now=root;
  int rank=0;
  while(5201314+love_nmr)
  {
    if(x<dat[now])
      now=son[now][0];
    else
    {
      rank+=siz[son[now][0]];
      if(x==dat[now])
      {
        splay(now,root);
        olinr rank+1;
      }
      rank+=num[now];
      now=son[now][1];
    }
  }
}
inline int n_rank_x(int x)
{
  int now=root;
  while(5201314+love_nmr)
  {
    if(siz[son[now][0]]>=x)
      now=son[now][0];
    else
    {
      if(num[now]+siz[son[now][0]]>=x)
        olinr dat[now];
      x-=(num[now]+siz[son[now][0]]);
      now=son[now][1];
    }
  }
}
inline int pre(int x)
{
  x_rank_n(x);
  int now=son[root][0];
  while(son[now][1])
    now=son[now][1];
  olinr now;
}
inline int nxt(int x)
{
  x_rank_n(x);
  int now=son[root][1];
  while(son[now][0])
    now=son[now][0];
  olinr now;
}
inline int del(int x)
{
  int l=pre(x);
  int r=nxt(x);
  splay(l,root);
  splay(r,son[root][1]);
  int now=son[son[root][1]][0];
  siz[now]--;
  num[now]--;
  if(!num[now])
  {
    son[fat[now]][0]=0;
    fat[now]=0;
  }
  splay(son[root][1],root);
}
inline void insert(int x)
{
  if(!root)
  {
    root=++cnt;
    siz[root]=1;
    dat[root]=x;
    num[root]=1;
    olinr;
  }
  int fa=0;
  int now=root;
  while(5201314+love_nmr)
  {
    if(dat[now]==x)
    {
      num[now]++;
      siz[now]++;
      splay(now,root);
      olinr;
    }
    fa=now;
    now=son[now][x>dat[now]];
    if(!now)
    {
      now=++cnt;
      fat[now]=fa;
      son[fa][x>dat[fa]]=now;
      num[now]++;
      siz[now]++;
      dat[now]=x;
      splay(now,root);
      olinr;
    }
  }
}
int main()
{
  n=read();
  int flag,x;
  insert(INF);
  insert(-INF);
  for(int i=1;i<=n;i++)
  {
    flag=read();
    x=read();
    if(flag==1) insert(x);
    if(flag==2) del(x);
    if(flag==3){put(x_rank_n(x)-1);putchar('\n');}
    if(flag==4){put(n_rank_x(x+1));putchar('\n');}
    if(flag==5){insert(x);put(dat[pre(x)]);putchar('\n');del(x);}
    if(flag==6){insert(x);put(dat[nxt(x)]);putchar('\n');del(x);}
  }
  olinr love_nmr;
}

注释QAQ

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;
#define R register
#define IL inline
#define INF 2147483640
#define mod 125125
#define II int
II root;      //根的编号                 
II n;         //n个操作 
II cnt;        //编号 
II fa[mod];      //fa[i]代表i的父亲 
II son[mod][2];    //son[i][0]代表i的左儿子，son[i][1]代表i的右儿子 
II data[mod];    //data[i]代表树上编号为i的点的值 
II size[mod];    //size[i]表示以i为根的子树的sum的和 (大小) (包括自己) 
II sum[mod];    //sum[i]表示数字i的个数 
IL II read()    //快读(有负数) 
{
  R II x=0,f=1;
  char ch=getchar();
  while(!isdigit(ch))
  {
    if(ch=='-')
      f=-f;
    ch=getchar();
  }
  while(isdigit(ch))
  {
    x=(x<<1)+(x<<3)+(ch^48);
    ch=getchar();
  }
  return x*f;
}
IL void update(R II x)  //更新x 
{
  size[x]=size[son[x][0]]+size[son[x][1]]+sum[x];
  //当前点的size == 左儿子的size + 右儿子的size + 当前点的个数 
}
IL void rotate(R II x,R II &o)  //旋转 
{
  R II y=fa[x];        //y为x的父亲 
  R II z=fa[y];        //z为y的父亲，z为x的爷爷 
  R bool xx=(son[y][1]==x);  //xx表示y的右儿子是否为x 
  R bool yy=xx^1;        //yy表示y的左儿子是否为x 
  if(y==o)           //x的父亲y是旋转的目标点 
    o=x;          //目标点变为x 
  else            //x的父亲y不是旋转的目标点 
    son[z][son  [z][1]==y]=x;  //如果z的右儿子是y，那么现在z的右儿子是x；如果z的右儿子不是y，那么现在z的左儿子是x 
  fa[x]=z;           //x的父亲是z 
  fa[y]=x;          //y的父亲是x(x转了上去) 
  fa[son[x][yy]]=y;      //如果原来y的左儿子是x，那么现在x的右儿子是y；如果原来y的右儿子是x，那么现在x的左儿子是y 
  son[y][xx]=son[x][yy];     //原来x的(右||左)儿子变成了先在y的(左||右)儿子 
  son[x][yy]=y;        //如果原来y的(左||右)儿子是x，那么现在x的(右||左)儿子是y 
  update(y);          //维护y 
  update(x);          //维护x 
}
IL void splay(R II x,R II &o)
{
  while(x!=o)                  //只要为转到目标节点 
  {              
    R II y=fa[x];              //y是x的父亲 
    R II z=fa[y];              //z是y的父亲，x的爷爷 
    if(y!=o)                //如果y不是目标节点 
    {
      if((son[y][0]==x)^(son[z][0]==y))  //如果xyz不在一条直链上 
        rotate(x,o);          //x朝o的方向转 
      else                //在一条直链上 
        rotate(y,o);          //转y 
    }                      
    rotate(x,o);              //转x 
  }
}
IL void insert(R II x)    
{
  if(!root)              //是根 
  {                  //初始化 
    root=++cnt;
    data[root]=x;
    size[root]=1;
    sum[root]=1;
    return;
  }
  R II now=root;            //从根开始找合适位置 
  R II fat=0;              //now的father          
  while(5201314)     
  {
    if(data[now]==x)         //树中已有该元素 
    {
      sum[now]++;          //累计数量 
      splay(now,root);      //转 
      return;
    }
    fat=now;
    now=son[now][data[now]<x];    //now往孩子上跳 
    if(!now)            //跳到了叶子的孩子(还没有) 
    {
      now=++cnt;          //初始化 
      fa[now]=fat;
      son[fat][data[fat]<x]=now;
      size[now]++;
      sum[now]++;
      data[now]=x;
      splay(now,root);
      return;
    }
  }
}
IL II x_rank_n(R II x)         //找树中的数x的排名 
{
  R II rank=0;           
  R II now=root;          //从根往下找 
  while(5201314)
  {
    if(x<data[now])        //小于当前点往左跳 
      now=son[now][0];
    else          
    {
      rank+=size[son[now][0]];//排名加上左子树大小(x一定比左子树所有值都大，不然就会往左跳) 
      if(x==data[now])    //找到了x 
      {
        splay(now,root);  //转上去 
        return rank+1;    //x的位置 
      }
      rank+=sum[now];      //往右跳说明它比前面所有数都大，所以要累计前面数的个数 
      now=son[now][1];    //累计完后在往后跳 
    }
  }
}
IL II rank_n_x(R II x)        
{
  R II rank=0;
  R II now=root;
  while(5201314)
  {
    if(size[son[now][0]]>=x)        //目标在左子树 
      now=son[now][0];          //往左跳 
    else
    {
      if(sum[now]+size[son[now][0]]>=x)   //now就是x的位置 
        return data[now];
      x-=(sum[now]+size[son[now][0]]);  //x减左边个数 
      now=son[now][1];          //再向右跳 
    }
  }
}
IL II pre(R II x)
{
  x_rank_n(x);
  R II now=son[root][0];
  while(son[now][1])
    now=son[now][1];
  return now;
}
IL II nxt(R II x)
{
  x_rank_n(x);
  R II now=son[root][1];
  while(son[now][0])
    now=son[now][0];
  return now;
}
IL void del(R II x)
{
  R II l=pre(x);
  R II r=nxt(x);
  splay(l,root);
  splay(r,son[root][1]);
  R II now=son[son[root][1]][0];
  sum[now]--;
  size[now]--;
  if(!sum[now])
  {
    son[fa[now]][0]=0;
    fa[now]=0;
  }
  splay(son[root][1],root);
}
int main()
{
  ios::sync_with_stdio(false);
  n=read();
  insert(-INF);
  insert(INF);
  for(R II i=1;i<=n;i++)
  {
    R II x=read();
    R II y=read();
    if(x==1) insert(y);
    if(x==2) del(y);
    if(x==3) printf("%d\n",x_rank_n(y)-1);
    if(x==4) printf("%d\n",rank_n_x(y+1));
    if(x==5) insert(y),printf("%d\n",data[pre(y)]),del(y);
    if(x==6) insert(y),printf("%d\n",data[nxt(y)]),del(y);
  }
  return 0;
}

----olinr

[C++] P3369 【模板】普通平衡树

上山打老虎 LV4