P6136

【模板】普通平衡树（数据加强版）

给一个自己的建议，学习平衡树真的不要太多，我个人觉得学会 FHQ-Treap（可以处理大部分需要平衡树的问题）和 Splay（主要是 LCT 必须要用）就够了。。。

学太多了我觉得大部分人应该很难背下来。。。我自己光是背这两个板子就花了相当的时间。。。

如果非要论优先级的话，建议先学 FHQ-Treap，它灵活性又好、代码又短还易于理解。。。

说实话普通 Treap 似乎不用学，因为这个东西除了常数小之外，功能相比于 FHQ-Treap 和 Splay 都要弱“一些”，更重要的是：代码真的也不短（可很多 OI 的书上都会写这个，而且还不写 FHQ-Treap）。。。

很多数据结构都是比较工具性的东西，真的。。。

虽然这两个平衡树据说常数很巨大，但我实在学不动了咕咕咕。

一、Splay

原来的题拿了一个 Treap 过了。

然后没有任何封装，导致模板很难再利用什么的，比如说在树套树上。

然后这里写了一个封装的 Splay。

应该比较好用。

但是没有卡常。所以直接加了 inline。好像也能快上不少。

可能 Splay 天生常数大跑不过 Treap 吧。

时间复杂度 $O((n+m)\log n)$。

$Update AD20220123$ 代码修改。使用指针写法为 Splay 动态分配内存，更加方便应用在树套树等嵌套数据结构上。

实际上比起单纯去理解，背掉代码反而能理解得更快。

1. Init。这个操作为一棵 Splay 分配大小为 $x$ 的内存空间。

2. Get。这个操作用来返回 $x$ 是左儿子还是右儿子。

3. Pushup。这个操作用来更新 $x$ 自身的子树大小（在不同的题可以有不同的用途，和线段树的 Pushup 类似）。

4. Clear。这个操作用来清空一个节点。

5. Rotate。这个操作是 Splay 的基础。

   然而总结起来就是：如果 $x$ 是 $y$ 的一边的儿子，则 $x$ 的另一边的儿子变成 $y$ 一边的儿子，$x$ 的另一边的儿子变成 $y$。

6. splay。这个操作是 Splay 的核心操作，一共有六种情况。然而背代码比背情况方便得多。而且代码背完之后就能很好的理解这六种情况了。

7. Find。这个操作是一个辅助操作，用来找到数值为 $k$ 的节点。

   具体操作就是和节点比大小决定往左还是往右。最后把找到的点 splay 到根节点。理论上来讲，如果说 Splay 中尚未插入这个节点，则这个操作返回的节点是前驱或后继。

8. Ins。这个操作是插入一个节点。

   首先若树是空的直接插入即可。否则，我们左右寻找即可，可以证明它一定可以找到一个空节点的位置插入。

9. Rk。不是 Mark 而是 Rk 因为没有马。原来我单门又写了一个函数实现，但实际上这个操作可以借助 Find 直接实现。

   判断一下它在根节点的左边还是右边即可（左边就直接输出左子树大小加一，右边就输出左子树大小加根节点大小加一）。

10. Kth。

    先判断与左子树的大小关系，如果大于等于的话减掉左子树和根节点，此时若小于等于零，则我们找到了该节点，先 splay 该节点再返回该节点，否则往右子树寻找；否则往左子树寻找。

11. Pre 与 Nxt。找前驱与后继。

    这里先 Find，然后如果根节点此时就是前驱或者后继直接返回即可。反之，以前驱为例，先走到左子树，再一直往右走，这个点就是前驱。后继同理。

    当然图省事的话直接 Rk 和 Kth 结合起来也是完全没有问题的（不过常数大一点）。

12. Del。这个操作会比想象中的复杂一些，因为多了一些特殊情况的讨论。

    先 Find，然后如果说这个点的大小大于一那么直接减大小即可。

    反之判断特殊情况，如果左右子树都没有，直接把树删完；若没有右子树或左子树，直接删根节点；反之找到根的前驱，前驱成为此时的根，则要删的点必然没有左子树，因此直接把它的右子树接给前驱，然后删除即可。

至此，Splay 的所有操作结束。

什么，如果有延迟标记怎么搞下传？请看文艺平衡树。

现在这个代码是我修的比较漂亮的状态了，但仍然有点长。（我见过最短的大概是 lxl 的 WBLT，大概不到百行，当然压行很厉害）

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=2e6;

ll n,m,ans,last,op,x;

ll buffa[N+5],bufch0[N+5],bufch1[N+5],bufcnt[N+5],bufsiz[N+5],bufval[N+5];
ll *nowfa=buffa,*nowch0=bufch0,*nowch1=bufch1,*nowcnt=bufcnt,
  *nowsiz=bufsiz,*nowval=bufval;

struct Splay{
  ll *fa,*ch[2],*cnt,*siz,*val;ll rt,sz;
  inline void Init(ll x) {
    fa=nowfa;ch[0]=nowch0;ch[1]=nowch1;cnt=nowcnt;siz=nowsiz;val=nowval;
    nowfa+=x+1;nowch0+=x+1;nowch1+=x+1;nowcnt+=x+1;nowsiz+=x+1;nowval+=x+1;
  }
  inline ll Get(ll x) {return x==ch[1][fa[x]];}
  inline void Pushup(ll x) {siz[x]=siz[ch[0][x]]+siz[ch[1][x]]+cnt[x];}
  inline void Clear(ll x) {fa[x]=ch[0][x]=ch[1][x]=cnt[x]=siz[x]=val[x]=0;}
  inline void Rotate(ll x) {
    ll y=fa[x],z=fa[y],c=Get(x);ch[c][y]=ch[c^1][x];
    if(ch[c^1][x]) fa[ch[c^1][x]]=y;ch[c^1][x]=y;fa[y]=x;fa[x]=z;
    if(z) ch[y==ch[1][z]][z]=x;Pushup(y);Pushup(x);
  }
  inline void splay(ll x,ll g) {
    for(ll f=fa[x];f=fa[x],f!=g;Rotate(x)) {
      if(fa[f]!=g) Rotate(Get(f)==Get(x)?f:x);
    }
    if(!g) rt=x;
  }
  inline ll Find(ll k) {
    if(!rt) return 0;ll cur=rt;
    while(ch[k>val[cur]][cur]&&k!=val[cur]) cur=ch[k>val[cur]][cur];
    splay(cur,0);return cur;
  }
  inline void Ins(ll k) {
    if(!rt) {val[rt=++sz]=k;cnt[sz]++;Pushup(sz);return;}
    ll cur=rt,f=0;
    while(1) {
      if(k==val[cur]) {
        cnt[cur]++;Pushup(cur);Pushup(f);splay(cur,0);break;
      }
      f=cur;cur=ch[k>val[cur]][cur];
      if(!cur) {
        val[++sz]=k;cnt[sz]++;fa[sz]=f;ch[k>val[f]][f]=sz;
        Pushup(sz);Pushup(f);splay(sz,0);break;
      }
    }
  }
  inline ll Rk(ll k) {
    Find(k);return k>val[rt]?siz[ch[0][rt]]+cnt[rt]+1:siz[ch[0][rt]]+1;
  }
  inline ll Kth(ll x) {
    ll cur=rt;
    while(1) {
      if(ch[0][cur]&&x<=siz[ch[0][cur]]) cur=ch[0][cur];
      else {
        x-=cnt[cur]+siz[ch[0][cur]];
        if(x<=0) return splay(cur,0),cur;cur=ch[1][cur];
      }
    }
  }
  inline ll Pre(ll k) {
    Find(k);if(k>val[rt]) return rt;ll cur=ch[0][rt];
    while(ch[1][cur]) cur=ch[1][cur];splay(cur,0);return cur;
  }
  inline ll Nxt(ll k) {
    Find(k);if(k<val[rt]) return rt;ll cur=ch[1][rt];
    while(ch[0][cur]) cur=ch[0][cur];splay(cur,0);return cur;
  }
  inline void Del(ll k) {
    Find(k);ll cur=rt;
    if(cnt[rt]>1) {cnt[rt]--;Pushup(rt);return;}
    if(!ch[0][rt]&&!ch[1][rt]) {Clear(rt);rt=0;return;}
    if(!ch[0][rt]) {rt=ch[1][rt];fa[rt]=0;Clear(cur);return;}
    if(!ch[1][rt]) {rt=ch[0][rt];fa[rt]=0;Clear(cur);return;}
    ll x=Pre(k);fa[ch[1][cur]]=x;ch[1][x]=ch[1][cur];Clear(cur);Pushup(x);
  }
}s;

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
  while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar('-');do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

int main() {

  n=read();m=read();s.Init(n+m);

  for(ll i=1;i<=n;i++) s.Ins(read());

  while(m--) {
    op=read();x=read()^last;
    if(op==1) {s.Ins(x);}
    if(op==2) {s.Del(x);}
    if(op==3) {last=s.Rk(x);ans^=last;}
    if(op==4) {last=s.val[s.Kth(x)];ans^=last;}
    if(op==5) {last=s.val[s.Pre(x)];ans^=last;}
    if(op==6) {last=s.val[s.Nxt(x)];ans^=last;}
  }

  write(ans);

  return 0;
}

二、FHQ-Treap

我来填坑了/kk。

我还是以这种类似代码注释的方式搞吧。

1. Init。和 Splay 类似，为 FHQ-Treap 动态分配大小为 $x$ 的内存。

2. Pushup。更新 $x$ 自身子树大小。

3. Clear。清空一个节点。

4. Split。这个是 FHQ-Treap 的重要操作之一。

   这里的 $x$ 和 $y$ 是两个虚拟节点，帮助我们索引分裂后的子树应该放到哪里（并且方便的分裂出确实的两个树）。

   我们分裂是根据权值与关键值 $k$ 的比较来的，简单来说，假如我们比较到节点 $p$，如果 $val(p)\le k$，显然 $p$ 及其左子树的所有节点都是权值小于等于 $k$ 的；反之就是 $p$ 及其右子树都是权值大于 $k$ 的。然后我们再递归处理另一个子树的分裂。

5. Merge。这个也是 FHQ-Treap 的重要操作之一。

   合并先从两颗 Treap 的根节点开始。很容易知道两个 Treap 实际上是有序的，并且我们默认左边的 Treap 是权值更小的。

   所以我们可以直接根据二者的随机键值来判断父子关系（需要满足堆性质）。然后讨论是 $x$ 和 $y$ 的左子树合并还是 $y$ 和 $x$ 的右子树合并即可。

   最后需要注意空节点的时候直接返回即可。

6. Ins。这个表示向 Treap 中插入一个数。

   这个我们先把 Treap 分裂成两部分，这两部分的权值正好夹着 $k$。然后先将 $k$ 与左子树合并，再将合并后的树与右子树合并（当然如果你喜欢也可以反过来）。

7. Rk。查询 $k$ 的排名。

   将 $k-1$ 作为关键值分裂出两颗子树。则左子树必然是所有权值小于 $k$ 的点。答案即为左子树大小加 1。然后我们再把两颗子树合并起来即可。

8. Kth。查询排名为 $k$ 的数。

   和 Splay 的差不多，只不过不需要 splay 操作了。我们直接根据子树大小和现排名的关系递归解决即可。

   实在觉得我懒可以去看上面 Splay 中这一操作的解释。

9. Pre 和 Nxt。懒了，直接用上面俩操作解决了，不解释。。。

   当然想要常数小一些的正规写法可以根据 $k-1$ 或 $k$ 分裂子树，然后查询左子树的最大值或者右子树的最小值。

10. Del。这个操作也比较好想。

    我们直接把 Treap 分成左子树，需要删除的节点，右子树，然后把左右子树合并即可。

实际上 FHQ-Treap 的很多操作都可以直接把普通 Treap 的操作搬过来，但是因为有了 Split 和 Merge 两个操作，这些普通的操作被大大简化，而且更加易于理解和记忆。

上传和下方懒标记同样鸽给文艺平衡树。

这里关于这个相同权值放在不同点的方式，我确实很无奈，因为我本来也想改成那种相同权值放在一个点的，但奈何又 T 又 WA 又 UB，心态实在爆炸，再加上这种不同点的写法又很亲民，那种查询有多少个 $k$ 之类的操作其实也很简单，就干脆不写了！（没错我就是鸽中鸽王）

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=2e6,inf=(1ll<<31)-1;

ll n,m,last,ans;
ll bufch[2][N+5],bufval[N+5],bufrnd[N+5],bufsiz[N+5];
ll *nowch[2]={bufch[0],bufch[1]},*nowval=bufval,*nowrnd=bufrnd
,*nowsiz=bufsiz;

struct Fhq_Treap{
  ll *ch[2],*val,*rnd,*siz;ll rt,sz;
  inline void Init(ll x) {
    ch[0]=nowch[0];ch[1]=nowch[1];val=nowval;rnd=nowrnd;siz=nowsiz;
    nowch[0]+=x+1;nowch[1]+=x+1;nowval+=x+1;nowrnd+=x+1;nowsiz+=x+1;
  }
  inline void Pushup(ll x) {siz[x]=siz[ch[0][x]]+siz[ch[1][x]]+1;}
  inline void Clear(ll x) {ch[0][x]=ch[1][x]=val[x]=rnd[x]=siz[x]=0;}
  inline void Split(ll p,ll k,ll &x,ll &y) {
    if(!p) {x=y=0;return;}
    if(val[p]<=k) {x=p;Split(ch[1][p],k,ch[1][p],y);}
    else {y=p;Split(ch[0][p],k,x,ch[0][p]);}
    Pushup(p);
  }
  inline ll Merge(ll x,ll y) {
    if(!x||!y) return x|y;
    if(rnd[x]<rnd[y]) {ch[0][y]=Merge(x,ch[0][y]);Pushup(y);return y;}
    else {ch[1][x]=Merge(ch[1][x],y);Pushup(x);return x;}
  }
  inline void Ins(ll k) {
    val[++sz]=k;siz[sz]=1;rnd[sz]=rand();
    if(!rt) {rt=sz;return;}
    ll x,y;Split(rt,k,x,y);rt=Merge(Merge(x,sz),y);
  }
  inline ll Rk(ll k) {
    ll x,y,ret;Split(rt,k-1,x,y);ret=siz[x]+1;Merge(x,y);return ret;
  }
  inline ll Kth(ll k) {
    ll p=rt;
    while(1) {
      if(k<=siz[ch[0][p]]) p=ch[0][p];
      else {k-=siz[ch[0][p]]+1;if(!k) return val[p];p=ch[1][p];}
    }
  }
  inline ll Pre(ll k) {return Kth(Rk(k)-1);}
  inline ll Nxt(ll k) {return Kth(Rk(k+1));}
  inline void Del(ll k) {
    ll x,y,z;Split(rt,k,x,z);Split(x,k-1,x,y);
    rt=Merge(Merge(x,Merge(ch[0][y],ch[1][y])),z);Clear(y);
  }
}t;

int main() {

  srand(19911225);
  n=read();m=read();t.Init(n+m+2);t.Ins(-inf);t.Ins(inf);
  for(ll i=1;i<=n;i++) {ll x=read();t.Ins(x);}

  for(ll i=1;i<=m;i++) {
    ll op,x;op=read();x=read()^last;
    if(op==1) {t.Ins(x);}
    if(op==2) {t.Del(x);}
    if(op==3) {last=t.Rk(x)-1;ans^=last;}
    if(op==4) {last=t.Kth(x+1);ans^=last;}
    if(op==5) {last=t.Pre(x);ans^=last;}
    if(op==6) {last=t.Nxt(x);ans^=last;}
  }

  write(ans);

  return 0;
}