平衡树Treap&Splay[学习笔记]

转载作者：撒哈拉更新时间：2024-05-25 09:04:11

平衡树 $\tt{Treap}$ & $\tt{Splay}$

壹.单旋 $\tt{Treap}$

首先了解 $\tt{BST}$ 。

非常好用的东西，但是数据可以把它卡成一条链 $\dots$ 。

于是，我们将 $\tt{Tree}$ 与 $\tt{heap}$ (堆) 合并，以保证平衡树 $\log$ 的深度.

具体地，我们可以使用旋转操作实现。

K8He的图。

以右旋为例，我们发现，本来的中序遍历顺序为 $y<p<x<q<z<r$，那么对于 $q$ 右旋，即将左儿子旋上来，由于本来 $p<q$ ，所以显然 $q$ 要成为 $p$ 的右儿子。那就剩下 $x$ 无家可归，我们发现 $p<x<q$，那么 $q$ 的左儿子再适合不过了.

我们规定 $0$ 方向为左，$1$ 方向为右，即可通过 $d$ ^ $1$ 实现方向取反.

一般的，对于一个节点 $i$，如果将其 $d$ 方向上的儿子 $s$ 旋上去，那么 $i$ 要成为 $s$ 在 $d$ ^ $1$ 方向上的儿子，$s$ 原来在 $d$ ^ $1$ 方向上的儿子要成为 $i$ 在 $d$ 方向上的儿子.

void rotate(int &i,int d){
    int s=t[i].son[d];
    t[i].son[d]=t[s].son[d^1];
    t[s].son[d^1]=i;
    up(i),i=s,up(i);
    return;
}

那么我们什么时候进行旋转呢？还记得我们说过要利用堆的性质，那么我们对每个节点随机一个优先级，将它按照小根堆或大根堆存，若当前不满足堆的性质了，那就旋转.

插入操作，从根往下跑，但要注意不满足堆的性质时，考虑旋转。

void insert(int &i,int k){
    if(!i){
        i=++tot;
        t[i].cnt=t[i].siz=1;
        t[i].val=k,t[i].rd=rnd();
        return;
    }
    t[i].siz++;
    if(t[i].val==k){
        ++t[i].cnt;return;
    }
    int d=(t[i].val<k);
    insert(t[i].son[d],k);
    if(t[i].rd>t[t[i].son[d]].rd)  rotate(i,d);
    return;
}

删除操作，先找节点，如果只有一个儿子，让儿子替换它，否则让儿子旋上来(当然要满足堆性质)，然后一直旋，直到剩一个儿子或者成为叶子节点。

void del(int &i,int k){
    if(!i)  return;
    if(t[i].val==k){
        if(t[i].cnt>1){
            --t[i].cnt,--t[i].siz;
            return;
        }
        int d=(t[ls(i)].rd>t[rs(i)].rd);
        if(!ls(i)||!rs(i))  i=ls(i)+rs(i);
        else  rotate(i,d),del(i,k);
        return;
    }
    t[i].siz--;
    int d=t[i].val<k;
    del(t[i].son[d],k);
    return;
}

查排名，看代码理解即可。

int rk(int i,int k){
    if(!i) return 1;
    if(t[i].val>k)  return rk(ls(i),k);
    if(t[i].val<k)  return t[ls(i)].siz+t[i].cnt+rk(rs(i),k);
    return t[ls(i)].siz+1;
}

查第 $k$ 大，思想和线段树一样。

int kth(int i,int k){
    while(1){
        if(k<=t[ls(i)].siz)  i=ls(i);
        else if(k>t[ls(i)].siz+t[i].cnt)
            k-=(t[ls(i)].siz+t[i].cnt),i=rs(i);
        else return t[i].val;
    }
}

前驱后继，和普通 $\tt{BST}$ 一样。

int pre(int i,int k){
    if(!i)  return -1e8;
    if(t[i].val>=k)  return pre(ls(i),k);
    return max(pre(rs(i),k),t[i].val);
}
int nex(int i,int k){
    if(!i)  return 1e8;
    if(t[i].val<=k)  return nex(rs(i),k);
    return min(nex(ls(i),k),t[i].val);
}

对于单旋 $\tt{Treap}$，我们只需要理解旋转操作即可，毕竟下面的 $\tt{Splay}$ 还要用它，请务必看懂旋转操作，其他的，还是FHQ好打，差不多看看就行，应用范围不大.

(板子封装在下面题单普通平衡树里) 。

贰.无旋 $\tt{FHQ\ Treap}$

由于单旋 $\tt{Treap}$ 不好打且扩展功能不多，所以我们引入新的 $\tt{FHQ\_ Treap}$，好像是神范浩强发明的，%%%%%%.

网上都说FHQ比单旋好理解，我表示理解了之后确实好理解，但你得先理解(我看了一个多小时才看懂，不过我是fw) 。

好那么直入正题 —— $\tt{FHQ\_ Treap}$ 。

既然也是 $\tt{Treap}$，那就是一样的，也是靠堆性质，它的不同之处就在于，它无旋，它是靠分裂+合并来保证 $\log$ 的深度.

具体地，分裂方式有两种，一种是按权值分裂，另一种是按照子树大小分裂

按照权值分裂，比如将以 $i$ 为根的平衡树分成两棵平衡树，根分别是 $x,y$，要求树 $x$ 的权值都小于等于 $k$,剩下是 $y$，那么分讨:
- 如果 $val(i)<=k$，那么 $i$ 的整棵左子树一定都小于 $k$，肯定都要划到 $x$ 里，则令 $x=i$，继续递归划分 $rs(i)$ 即可。
- 否则，$i$ 的整棵右子树一定都大于 $k$，肯定都要划到 $y$ 里，则令 $y=i$，继续递归划分 $ls(i)$ 即可。

注意取地址.

void split(int i,int k,int &x,int &y){
    if(!i){x=y=0;return;}
    if(val(i)>k)   y=i,split(ls(i),k,x,ls(i));
    if(val(i)<=k)  x=i,split(rs(i),k,rs(i),y);
    up(i);return;
}

按照子树大小分裂，还是将以 $i$ 为根的平衡树分成两棵平衡树，根分别是 $x,y$，要求是 $siz(x)=k$，还是和上面一样:
- 如果 $siz(ls(i))+cnt(i)<=k$，那么 $i$ 的整棵左子树和 $i$ 肯定都要划到 $x$ 里，则令 $x=i$，继续递归划分 $rs(i)$ 即可。
- 否则，$i$ 的整棵右子树肯定都要划到 $y$ 里，则令 $y=i$，继续递归划分 $ls(i)$ 即可。

按子树大小分裂，一般用在平衡树维护序列，后面的 $\tt{Splay}$ 也是一样.

void split(int i,int k,int &x,int &y){
    if(!i){x=y=0;return;}
    if(siz(ls(i))+cnt(i)<=k)  x=i,split(rs(i),k-(siz(ls(i))+cnt(i)),rs(i),y);
    else  y=i,split(ls(i),k,x,ls(i));
    up(i);
}

下一个操作是合并，$\tt{FHQ\_ Treap}$ 正是通过它保证的堆性质，设要合并的两棵树的根分别为 $x,y$，设堆性质为大根堆。
- 若 $rd(x)>rd(y)$ 则把 $x$ 定为根，然后继续递归合并 $rs(x)$ 和 $y$
- 否则把 $y$ 定为根，然后继续递归合并 $x$ 和 $ls(y)$

void merge(int &i,int x,int y){
    if(!x||!y){i=x|y;return;}
    if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
    else  merge(ls(y),x,ls(y)),i=y;
    up(i);return;
}

插入 $k$，先分裂出 $<=k-1$，合并时把 $k$ 合并进去。

void insert(int k){
    int rt1,rt2;
    split(rt,k-1,rt1,rt2);
    merge(rt,rt1,New(k));merge(rt,rt,rt2);
    return;
}

删除 $k$，把 $k$ 分裂出来，然后把 $k$ 用它的左右子树合并替代，再合并。

void del(int k){
    int rt1,rt2,cut;
    split(rt,k-1,rt1,rt2);split(rt2,k,cut,rt2);
    merge(cut,ls(cut),rs(cut));
    merge(rt,rt1,cut);merge(rt,rt,rt2);
    return;
}

查排名，分裂完 $\leq k-1$ 的树大小 $+1$

int rk(int i,int k){
    int rt1,rt2,res;
    split(i,k-1,rt1,rt2);
    res=siz(rt1)+1;
    merge(i,rt1,rt2);
    return res;
}

第 $k$ 小，和普通 $\tt{Treap}$ 一样.
前驱后继，以前驱为例，分裂出 $\leq k-1$，那么这部分都小于 $k$，找出最大值即可，一直跑右儿子，后继同理.

int pre(int &i,int k){
    int rt1,rt2,res;
    split(i,k-1,rt1,rt2),res=rt1;
    while(rs(res))  res=rs(res);
    merge(i,rt1,rt2);
    return val(res);
}
int nxt(int &i,int k){
    int rt1,rt2,res;
    split(i,k,rt1,rt2),res=rt2;
    while(ls(res))  res=ls(res);
    merge(i,rt1,rt2);
    return val(res);
}

(板子封装在下面题单普通平衡树里) 。

叁.双旋 $\tt{Splay}$

$\tt{Splay}$ 不同于以上两种 $\tt{Treap}$，它不再依靠随机的优先级保证深度，而是通过不断旋转来达到目的.

类似于单旋，只不过单旋是将某节点的儿子旋上来，而 $\tt{Splay}$ 是将某节点自身旋上去，单次旋转和 $\tt{Treap}$ 一样，但是要多记录一个父亲。

具体地，旋转 $x$ 时，令 $y$ 为 $x$ 的父亲，$z$ 为祖父，设 $x$ 为 $y$ 在 $d$ 方向上的儿子，则单次旋转可分为这几步

$x$ 替换 $y$ 成为 $z$ 的儿子
$x$ 在 $d$ ^ $1$ 方向的儿子下放给 $y$ 当 $d$ 方向的儿子
$y$ 充当 $x$ 在 $d$ ^ $1$ 方向的儿子

三次修改，三次认爹，rotate就写完了。

#define ds(i) t[i].son[d]
#define bs(i) t[i].son[d^1] 
void rotate(int x){
    int y=fa(x),z=fa(y);
    int d=(rs(y)==x);
    t[z].son[(rs(z)==y)]=x;fa(x)=z;
    ds(y)=bs(x);fa(bs(x))=y;
    bs(x)=y;fa(y)=x;
    up(y),up(x);
}

然后便是 $\tt{Splay}$ 的核心操作，splay 如说。

具体地，splay 操作是将节点 $x$ 旋转到目标节点 $s$ 的儿子，若 $s=0$ 则为旋转到根。那么如果我们一直一直单旋上去的话我们会发现一个严重的问题——虽然 $x$ 上去了，但是它的最大深度依然没变，也就是说，转了个寂寞。.

那么怎么办，进行双旋，讨论几种情况——($x,y,z$ 意义同上) 。

$z=s$ 直接将 $x$ 单旋一次上去。
$z\not ={s}$ 。
- $x,y,z$ 三点共线，即
此时我们应先转 $y$ 再转 $x$ 。

- 。
- $x,y,z$ 三点不共线，直接旋转两次 $x$
- 。

就这样旋旋旋，就能保证深度OK，每次插入节点后都要进行一次 Splay 。

void splay(int x,int s){
    while(fa(x)!=s){
        int y=fa(x),z=fa(y);
        if(z!=s)
            (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
        rotate(x);
    }
    if(!s)  rt=x;
}

至于这么旋为什么可以让复杂度OK，使用什么"势能分析法"，我是fw我不会.

$\tt{Splay}$ 与 $\tt{FHQ}$ 一样，也是两种维护方式，一种维护权值，一种维护下标(即序列的中序遍历).

然后就是 $\tt{Splay}$ 的一些基本操作

插入，有两种方式，即按权值和子树大小，与 $\tt{FHQ}$ 类似，注意要记录一下父亲节点。

按照权值插入

void insert(int k){
    int p=rt,f=0;
    while(p&&val(p)!=k){
        f=p;
        p=t[p].son[val(p)<k];
    }
    if(p)  ++cnt(p);
    else{
        p=++tot;
        if(f)  t[f].son[val(f)<k]=p;
        val(p)=k;fa(p)=f;
        siz(p)=cnt(p)=1;
    }
    splay(p,0);
}

按照子树大小插入，可以递归写(爱咋写咋写)

void insert(int &i,int f,int x,int k){
    if(!i){
        i=++tot;
        siz(i)=1;fa(i)=f;val(i)=k;
        return;
    }
    if(x<=siz(ls(i))+1)  insert(ls(i),i,x,k);
    else  insert(rs(i),i,x-siz(ls(i))-1,k);
    up(i);
}

对于splay，我们要先找到某权值对应的节点，直接找然后splay 。

权值

void find(int k){
    if(!rt)  return;
    int p=rt;
    while(t[p].son[val(p)<k]&&val(p)!=k){
        p=t[p].son[val(p)<k];
    }
    splay(p,0);
}

子树大小

void find(int x){
    if(!rt)  return;
    int p=rt;
    while(siz(ls(p))+1!=x){
        if(x<=siz(ls(p))+1){
            p=ls(p);
        }
        else{
            x-=(siz(ls(p))+1);
            p=rs(p);
        }
    }
    splay(p,0);
}

查第 $k$ 小，与 $\tt{Treap}$ 同理，不再赘述。
查排名，转到根节点后左子树的大小 $+1$ 即可。
查前驱后继，以前驱为例，转到根之后左子树里最大值即前驱，后继同理。
删除比较有意思，我们先找到前驱后继，然后将前驱splay到根，将后继splay到前驱的右儿子，那么要删除的节点就一定为 $ls(rs(rt))$ (如下图)。这也就意味着必须有前驱后继，否则删不了，那么直接插入两个极值哨兵节点即可.

     pre
    /   \
  ...   nxt
        /  \
      cut  ...

void del(int k){
    int prek=pre(k);
    int nxtk=nxt(k);
    splay(prek,0);splay(nxtk,prek);
    int cut=ls(nxtk);
    if(cnt(cut)>1)
        --cnt(cut),splay(cut,0);
    else  ls(nxtk)=0;
}

另外，维护序列的 $\tt{Splay}$ 进行区间操作时，也是将区间转化为子树,和删除操作类似，比如文艺平衡树就是这样，不再赘述.

最后注意一定要插哨兵。

(板子封装在下面题单普通平衡树里) 。

肆.$hs$题单

$T_D$ 普通平衡树

由于是纯板子，所以先挂 $T_D$.

普通Treap

#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 100010
int m;

namespace TREAP{
    mt19937 rnd(0x7f);
    struct Treap{
        int son[2],cnt,siz,val,rd;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
    }t[N];
    int tot,rt;
    void up(int i){
        t[i].siz=t[ls(i)].siz+t[rs(i)].siz+t[i].cnt;
    }
    void rotate(int &i,int d){
        int s=t[i].son[d];
        t[i].son[d]=t[s].son[d^1];
        t[s].son[d^1]=i;
        up(i),i=s,up(i);
        return;
    }
    void insert(int &i,int k){
        if(!i){
            i=++tot;
            t[i].cnt=t[i].siz=1;
            t[i].val=k,t[i].rd=rnd();
            return;
        }
        t[i].siz++;
        if(t[i].val==k){
            ++t[i].cnt;return;
        }
        int d=(t[i].val<k);
        insert(t[i].son[d],k);
        if(t[i].rd>t[t[i].son[d]].rd)  rotate(i,d);
        return;
    }
    void del(int &i,int k){
        if(!i)  return;
        if(t[i].val==k){
            if(t[i].cnt>1){
                --t[i].cnt,--t[i].siz;
                return;
            }
            int d=(t[ls(i)].rd>t[rs(i)].rd);
            if(!ls(i)||!rs(i))  i=ls(i)+rs(i);
            else  rotate(i,d),del(i,k);
            return;
        }
        t[i].siz--;
        int d=t[i].val<k;
        del(t[i].son[d],k);
        return;
    }
    int rk(int i,int k){
        if(!i) return 1;
        if(t[i].val>k)  return rk(ls(i),k);
        if(t[i].val<k)  return t[ls(i)].siz+t[i].cnt+rk(rs(i),k);
        return t[ls(i)].siz+1;
    }
    int kth(int i,int k){
        while(1){
            if(k<=t[ls(i)].siz)  i=ls(i);
            else if(k>t[ls(i)].siz+t[i].cnt)
                k-=(t[ls(i)].siz+t[i].cnt),i=rs(i);
            else return t[i].val;
        }
    }
    int pre(int i,int k){
        if(!i)  return -1e8;
        if(t[i].val>=k)  return pre(ls(i),k);
        return max(pre(rs(i),k),t[i].val);
    }
    int nex(int i,int k){
        if(!i)  return 1e8;
        if(t[i].val<=k)  return nex(rs(i),k);
        return min(nex(ls(i),k),t[i].val);
    }
} using namespace TREAP;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    m=read;
    int op,x;
    while(m-->0){
        op=read,x=read;
        switch(op){
            case 1:
                insert(rt,x);break;
            case 2:
                del(rt,x);break;
            case 3:
                write(rk(rt,x));pt;break;
            case 4:
                write(kth(rt,x));pt;break;
            case 5:
                write(pre(rt,x));pt;break;
            case 6:
                write(nex(rt,x));pt;break;
        }
    }

    return 0;
}

FHQ_Treap

#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=1e5+10;
namespace FHQ_TREAP{
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=cnt(i)+siz(ls(i))+siz(rs(i));
    }
    int New(int k){
        val(++tot)=k;
        cnt(tot)=siz(tot)=1;
        rd(tot)=rand();
        return tot;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)>k)   y=i,split(ls(i),k,x,ls(i));
        if(val(i)<=k)  x=i,split(rs(i),k,rs(i),y);
        up(i);return;
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);return;
    }
    void insert(int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));merge(rt,rt,rt2);
        return;
    }
    void del(int k){
        int rt1,rt2,cut;
        split(rt,k-1,rt1,rt2);split(rt2,k,cut,rt2);
        merge(cut,ls(cut),rs(cut));
        merge(rt,rt1,cut);merge(rt,rt,rt2);
        return;
    }
    int rk(int i,int k){
        int rt1,rt2,res;
        split(i,k-1,rt1,rt2);
        res=siz(rt1)+1;
        merge(i,rt1,rt2);
        return res;
    }
    int kth(int i,int k){
        while(1){
            if(k<=siz(ls(i)))  i=ls(i);
            else if(k>siz(ls(i))+cnt(i))
                k-=(siz(ls(i))+cnt(i)),i=rs(i);
            else return val(i);
        }
    }
    int pre(int &i,int k){
        int rt1,rt2,res;
        split(i,k-1,rt1,rt2),res=rt1;
        while(rs(res))  res=rs(res);
        merge(i,rt1,rt2);
        return val(res);
    }
    int nxt(int &i,int k){
        int rt1,rt2,res;
        split(i,k,rt1,rt2),res=rt2;
        while(ls(res))  res=ls(res);
        merge(i,rt1,rt2);
        return val(res);
    }
} using namespace FHQ_TREAP;
int m;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    srand(time(0));
    m=read;
    int op,x;
    while(m-->0){
        op=read,x=read;
        switch(op){
            case 1:
                insert(x);
                break;
            case 2:
                del(x);
                break;
            case 3:
                write(rk(rt,x));pt;
                break;
            case 4:
                write(kth(rt,x));pt;
                break;
            case 5:
                write(pre(rt,x));pt;
                break;
            case 6:
                write(nxt(rt,x));pt;
                break;
            default:break;
        }
    }
    return 0;
}

Splay

#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n;
namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[(rs(z)==y)]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    void find(int k){
        if(!rt)  return;
        int p=rt;
        while(t[p].son[val(p)<k]&&val(p)!=k){
            p=t[p].son[val(p)<k];
        }
        splay(p,0);
    }
    void insert(int k){
        int p=rt,f=0;
        while(p&&val(p)!=k){
            f=p;
            p=t[p].son[val(p)<k];
        }
        if(p)  ++cnt(p);
        else{
            p=++tot;
            if(f)  t[f].son[val(f)<k]=p;
            val(p)=k;fa(p)=f;
            siz(p)=cnt(p)=1;
        }
        splay(p,0);
    }
    int pre(int k){
        find(k);int p=rt;
        if(val(p)<k)  return p;
        p=ls(p);while(rs(p))  p=rs(p);
        return p;
    }
    int nxt(int k){
        find(k);int p=rt;
        if(val(p)>k)  return p;
        p=rs(p);while(ls(p))  p=ls(p);
        return p;
    }
    void del(int k){
        int prek=pre(k);
        int nxtk=nxt(k);
        splay(prek,0);splay(nxtk,prek);
        int cut=ls(nxtk);
        if(cnt(cut)>1)
            --cnt(cut),splay(cut,0);
        else  ls(nxtk)=0;
    }
    int kth(int k){
        int i=rt;
        if(siz(i)<k)  return 1;
        while(1){
            if(k<=siz(ls(i)))  i=ls(i);
            else if(k>siz(ls(i))+cnt(i))
                k-=(siz(ls(i))+cnt(i)),i=rs(i);
            else  return val(i);
        }
    }
} using namespace SPLAY;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    insert(-1e8);insert(1e8);
    int op,x;
    for(int i=1;i<=n;i++){
        op=read,x=read;
        switch(op){
        case 1:
            insert(x);break;
        case 2:
            del(x);break;
        case 3:
            find(x);
            write(siz(ls(rt))),pt;break;
        case 4:
            write(kth(x+1)),pt;break;
        case 5:
            write(val(pre(x))),pt;break;
        case 6:
            write(val(nxt(x))),pt;break;
        default:
            break;
        }
    }

    return 0;
}

$T_A$ 营业额统计

板子，求前驱后继.

普通Treap

#include<bits/stdc++.h>
using namespace std;
#define inf 1e10
#define int long long
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=(1<<15)+10;
int n;
int a;
int ans;
namespace TREAP{
    mt19937 Rand(0x7f);
    int tot,rt;
    struct Treap{
        int son[2],val,rd;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define val(i) t[i].val
        #define rd(i) t[i].rd
    }t[N];
    void rotate(int &i,int d){
        int s=t[i].son[d];
        t[i].son[d]=t[s].son[d^1];
        t[s].son[d^1]=i;
        i=s;
        return;
    }
    void insert(int &i,int k){
        if(!i){
            i=++tot;
            val(i)=k;rd(i)=Rand();
            return;
        }
        if(val(i)==k){
            return;
        }
        int d=(val(i)<k);
        insert(t[i].son[d],k);
        if(rd(i)>rd(t[i].son[d]))  rotate(i,d);
    }
    int pre(int i,int k){
        if(!i)  return -inf;
        if(val(i)>k)  return pre(ls(i),k);
        return max(val(i),pre(rs(i),k));
    }
    int nxt(int i,int k){
        if(!i)  return inf;
        if(val(i)<k)  return nxt(rs(i),k);
        return min(val(i),nxt(ls(i),k));
    }
} using namespace TREAP;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    a=read;
    ans=a;
    insert(rt,a);
    for(int i=2;i<=n;i++){
        a=read;
        int prea=pre(rt,a);
        int nxta=nxt(rt,a);
        ans+=min(a-prea,nxta-a);
        insert(rt,a);
    }
    write(ans);
    return 0;
}

FHQ_Treap

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = (1<<15)+10;

namespace FHQ_TREAP{
    mt19937 Rand(0x7f);
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=cnt(i)+siz(ls(i))+siz(rs(i));
    }
    int New(int k){
        val(++tot)=k;
        cnt(tot)=siz(tot)=1;
        rd(tot)=Rand();
        return tot;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)>k)  y=i,split(ls(i),k,x,ls(i));
        if(val(i)<=k) x=i,split(rs(i),k,rs(i),y);
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    int pre(int k){
        int rt1,rt2;
        split(rt,k,rt1,rt2);
        if(!siz(rt1))  return -1e8;
        int res=rt1;
        while(rs(res))  res=rs(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    int nxt(int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        if(!siz(rt2))  return 1e8;
        int res=rt2;
        while(ls(res))  res=ls(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
} using namespace FHQ_TREAP;
int n,a;
int ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    a=read;
    insert(a);
    ans=a;
    for(int i=2;i<=n;i++){
        a=read;
        int prea=pre(a);
        int nxta=nxt(a);
        ans+=min(a-prea,nxta-a);
        insert(a);
    }
    write(ans);
    return 0;
}

Splay

#include<bits/stdc++.h>
using namespace std;
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n;
namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[(rs(z)==y)]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    void find(int k){
        if(!rt)  return;
        int p=rt;
        while(t[p].son[val(p)<k]&&val(p)!=k){
            p=t[p].son[val(p)<k];
        }
        splay(p,0);
    }
    void insert(int k){
        int p=rt,f=0;
        while(p&&val(p)!=k){
            f=p;
            p=t[p].son[val(p)<k];
        }
        if(p)  ++cnt(p);
        else{
            p=++tot;
            if(f)  t[f].son[val(f)<k]=p;
            val(p)=k;fa(p)=f;
            siz(p)=cnt(p)=1;
        }
        splay(p,0);
    }
    int pre(int k){
        find(k);int p=rt;
        if(val(p)<=k)  return p;
        p=ls(p);while(rs(p))  p=rs(p);
        return p;
    }
    int nxt(int k){
        find(k);int p=rt;
        if(val(p)>=k)  return p;
        p=rs(p);while(ls(p))  p=ls(p);
        return p;
    }
} using namespace SPLAY;
int a,ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    insert(-1e8);insert(1e8);
    a=read;
    ans=a;
    insert(a);
    for(int i=2;i<=n;i++){
        a=read;
        int prea=val(pre(a)),nxta=val(nxt(a));
        ans+=min(a-prea,nxta-a);
        insert(a);
    }
    write(ans);

    return 0;
}

$T_B$ 宠物收养所

发现某时刻的平衡树里只会全是人或者全是狗，查前驱后继即可，查完即删.

普通Treap

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1e10
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N=8*1e4+10;
const int p=1e6;
int n;
namespace TREAP{
    mt19937 Rand(0x7f);
    struct Treap{
        int son[2],cnt,siz,val,rd;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
        #define rd(i) t[i].rd
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void rotate(int &i,int d){
        int s=t[i].son[d];
        t[i].son[d]=t[s].son[d^1];
        t[s].son[d^1]=i;
        up(i),i=s,up(i);
        return;
    }
    void insert(int &i,int k){
        if(!i){
            i=++tot;
            cnt(i)=siz(i)=1;
            val(i)=k;rd(i)=Rand();
            return;
        }
        siz(i)++;
        if(val(i)==k){
            cnt(i)++;return;
        }
        int d=(val(i)<k);
        insert(t[i].son[d],k);
        if(rd(i)>rd(t[i].son[d]))  rotate(i,d);
        return;
    }
    void del(int &i,int k){
        if(!i)  return;
        if(val(i)==k){
            if(cnt(i)>1){
                --cnt(i),--siz(i);
                return;
            }
            int d=(rd(ls(i))>rd(rs(i)));
            if(!ls(i)||!rs(i))  i=ls(i)+rs(i);
            else  rotate(i,d),del(i,k);
            return;
        }
        int d=(val(i)<k);
        --siz(i);
        del(t[i].son[d],k);
        return;
    }
    int pre(int i,int k){
        if(!i)  return -inf;
        if(val(i)>k)  return pre(ls(i),k);
        return max(val(i),pre(rs(i),k));
    }
    int nxt(int i,int k){
        if(!i)  return inf;
        if(val(i)<k)  return nxt(rs(i),k);
        return min(val(i),nxt(ls(i),k));
    }
} using namespace TREAP;

int num[2];
bool now,a;
int b;
int ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    now=read;
    num[now]++;
    b=read;insert(rt,b);
    for(int i=2;i<=n;i++){
        a=read,b=read;
        if(!num[a^1]){
            num[a]++;insert(rt,b);
            now=a;
            continue;
        }
        if(now^a){
            int preb=pre(rt,b);
            int nxtb=nxt(rt,b);
            int hwr=(b-preb<=nxtb-b?preb:nxtb);
            ans=(ans+abs(hwr-b))%p;
            del(rt,hwr);
            --num[now];
        }
        else
            insert(rt,b),++num[now];
    }
    write(ans);
    return 0;
}

Splay

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1e10
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 8*1e4+10;
const int p = 1e6;
int n;

namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[(rs(z)==y)]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    void insert(int k){
        int p=rt,f=0;
        while(p && val(p)!=k){
            f=p;
            p=t[p].son[val(p)<k];
        }
        if(p)  ++cnt(p);
        else{
            p=++tot;
            if(f)  t[f].son[val(f)<k]=p;
            val(p)=k;fa(p)=f;
            siz(p)=cnt(p)=1;
        }
        splay(p,0);
    }
    void find(int k){
        if(!rt)  return;
        int p=rt;
        while(t[p].son[val(p)<k] && val(p)!=k){
            p=t[p].son[val(p)<k];
        }
        splay(p,0);
    }
    int pre(int k,bool b){
        find(k);int p=rt;
        if(val(p)==k&&b)  return p;
        if(val(p)<k)  return p;
        p=ls(p);while(rs(p))  p=rs(p);
        return p;
    }
    int nxt(int k,bool b){
        find(k);int p=rt;
        if(val(p)==k&&b)  return p;
        if(val(p)>k)  return p;
        p=rs(p);while(ls(p))  p=ls(p);
        return p;
    }
    void del(int k){
        int prek=pre(k,0),nxtk=nxt(k,0);
        splay(prek,0);splay(nxtk,prek);
        int cut=ls(nxtk);
        if(cnt(cut)>1)  --cnt(cut),splay(cut,0);
        else  ls(nxtk)=0;
    }
} 
using namespace SPLAY;
bool now;
int num[2];
int a,b;
int ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    insert(-inf);insert(inf);
    n=read;
    now=read;b=read;num[now]=1;
    insert(b);
    for(int i=2;i<=n;i++){
        a=read,b=read;
        if(!num[a^1]){
            ++num[a],now=a;
            insert(b);
            continue;
        }
        if(a==now){
            ++num[now];
            insert(b);
        }
        else{
            int preb=val(pre(b,1)),nxtb=val(nxt(b,1));
            int hwr=(b-preb<=nxtb-b?preb:nxtb);
            ans=(ans+abs(hwr-b))%p;
            del(hwr);
            --num[now];
        }
    }
    write(ans);
    return 0;
}

注意 $Splay$ 求前驱后继时如果要取等注意特判，删除时不可取等(取等就寄了) 。

$T_C$ 郁闷的出纳员

维护整体懒标记，每次删除低于 $minn-add$ 线的.

用普通 $\tt{Treap}$ 直接暴力删，不好打。
用 $\tt{FHQ\_ Treap}$ 分裂出低于 $minn-add$ 的部分，直接不要即可。

服了，$\tt{FHQ\_ Treap}$ 跑不过普通 $\tt{Treap}$ 的暴力。。.

普通Treap

#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e6;
int n,minn;
int add;
int ans,sum;
int num;
namespace TREAP{
    mt19937 rnd(0x7f);
    struct Treap{
        int son[2],cnt,siz,val,rd;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define val(i) t[i].val
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
    }t[N];
    int tot,rt;
    void up(int i){
        t[i].siz=t[ls(i)].siz+t[rs(i)].siz+t[i].cnt;
    }
    void rotate(int &i,int d){
        int s=t[i].son[d];
        t[i].son[d]=t[s].son[d^1];
        t[s].son[d^1]=i;
        up(i),i=s,up(i);
        return;
    }
    void insert(int &i,int k){
        if(!i){
            i=++tot;
            t[i].cnt=t[i].siz=1;
            t[i].val=k,t[i].rd=rnd();
            return;
        }
        t[i].siz++;
        if(t[i].val==k){
            ++t[i].cnt;return;
        }
        int d=(t[i].val<k);
        insert(t[i].son[d],k);
        if(t[i].rd>t[t[i].son[d]].rd)  rotate(i,d);
        return;
    }
    void del(int &i,int k){
        if(!i)  return;
        if(t[i].val==k){
            if(t[i].cnt>1){
                --t[i].cnt,--t[i].siz;
                return;
            }
            int d=(t[ls(i)].rd>t[rs(i)].rd);
            if(!ls(i)||!rs(i))  i=ls(i)+rs(i);
            else  rotate(i,d),del(i,k);
            return;
        }
        t[i].siz--;
        int d=(t[i].val<k);
        del(t[i].son[d],k);
        return;
    }
    int rk(int i,int k){
        if(!i) return 0;
        if(t[i].val>k)  return rk(ls(i),k);
        if(t[i].val<k)  return t[ls(i)].siz+t[i].cnt+rk(rs(i),k);
        return t[ls(i)].siz+1;
    }
    int find(int i,int k){
        while(1){
            if(k<=t[ls(i)].siz)  i=ls(i);
            else if(k>t[ls(i)].siz+t[i].cnt)
                k-=(t[ls(i)].siz+t[i].cnt),i=rs(i);
            else return t[i].val;
        }
    }
    void dfs(int x){
        if(ls(x))  dfs(ls(x));
        if(rs(x))  dfs(rs(x));
        if(minn-add>val(x)){
            int c=cnt(x);
            for(int i=1;i<=c;i++)
                del(rt,val(x));
        }
    }

} using namespace TREAP;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,minn=read;
    char op;
    int k;
    for(int i=1;i<=n;i++){
        cin>>op;k=read;
        switch (op){
            case 'I':
                if(k>=minn)  insert(rt,k-add),++num; 
                break;
            case 'A':
                add+=k;
                break;
            case 'S':
                add-=k;
                dfs(rt);
                break;
            case 'F':
                if(siz(rt)<k)  ans=-1;
                else ans=find(rt,siz(rt)-k+1)+add;
                write(ans);pt;
                break;
            default:
                break;
        }
    }
    write(num-siz(rt));
    return 0;
}

FHQ_Treap

#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n,minn,add;

namespace FHQ_TREAP{
    mt19937 Rand(0x7f);
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    int New(int k){
        val(++tot)=k;
        siz(tot)=cnt(tot)=1;
        rd(tot)=Rand();
        return tot;
    }
    void spilt(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)>k)  y=i,spilt(ls(i),k,x,ls(i));
        if(val(i)<=k) x=i,spilt(rs(i),k,rs(i),y);
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int k){
        int rt1,rt2;
        spilt(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
        return;
    }
    void del(int k){
        int rt1,rt2;
        spilt(rt,k-1,rt1,rt2);
        rt=rt2;
    }
    int kth(int i,int k){
        while(1){
            if(k<=siz(ls(i)))  i=ls(i);
            else if(k>siz(ls(i))+cnt(i))
                k-=(siz(ls(i))+cnt(i)),i=rs(i);
            else return val(i);
        }
    }
} using namespace FHQ_TREAP;

int sum,ans;
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,minn=read;
    char op;
    int k;
    for(int i=1;i<=n;i++){
        cin>>op;k=read;
        switch(op){
            case 'I':
                if(k>=minn)
                    insert(k-add),++sum;
                break;
            case 'A':
                add+=k;
                break;
            case 'S':
                add-=k;
                del(minn-add);
                break;
            case 'F':
                if(siz(rt)<k)  ans=-1;
                else  ans=kth(rt,siz(rt)-k+1)+add;
                write(ans);pt;
                break;
        }
    }
    write(sum-siz(rt));
    return 0;
}

$T_E$ 文艺平衡树

平衡树不仅具有二叉搜索树的功能，同样可以支持区间操作，即，将序列的下标塞进平衡树，它的中序遍历就是原序列，然后我们想干嘛就干嘛~ 。

对于区间翻转，考虑维护懒标记，下放时交换左右儿子，分别异或。最后中序遍历输出每个节点的值.

对于打懒标记，分裂出 $[l,r]$ 部分，一定要先分出前 $r$ 个，再分前 $l-1$ 个，反过来如果先分前 $l-1$ 个，后面就应该分出 $r-l+1$ 个，手画一下就知道为什么了.

这里使用 $\tt{FHQ\_ Treap}$ 时，我们按子树大小进行分裂，因为我们是按照下标建的树，不能按权值分裂.

FHQ_Treap

#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n,m;

namespace FHQ_TREAP{
    struct Treap{
        int son[2],val,cnt,siz,rd,lazy;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
        #define lazy(i) t[i].lazy
    }t[N];
    int tot,rt;
    int New(int k){
        val(++tot)=k;
        cnt(tot)=siz(tot)=1;
        rd(tot)=rand();
        return tot;
    }
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    void down(int i){
        if(!lazy(i))  return;
        swap(ls(i),rs(i));
        lazy(ls(i))^=1;
        lazy(rs(i))^=1;
        lazy(i)=0;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        down(i);
        if(siz(ls(i))+cnt(i)<=k)  x=i,split(rs(i),k-(siz(ls(i))+cnt(i)),rs(i),y);
        else  y=i,split(ls(i),k,x,ls(i));
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  down(x),merge(rs(x),rs(x),y),i=x;
        else  down(y),merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int k){
        int rt1,rt2;
        split(rt,k,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    void out(int i){
        down(i);
        if(ls(i))  out(ls(i));
        write(val(i));putchar(' ');
        if(rs(i))  out(rs(i));
    }
} using namespace FHQ_TREAP;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    srand(time(0));
    n=read,m=read;
    for(int i=1;i<=n;i++)  insert(i);
    int l,r,rt1,rt2,rt3;
    for(int i=1;i<=m;i++){
        l=read,r=read;
        rt1=rt2=rt3=0;
        split(rt,r,rt1,rt3);
        split(rt1,l-1,rt1,rt2);
        lazy(rt2)^=1;
        merge(rt1,rt1,rt2);
        merge(rt,rt1,rt3);
        // split(rt,l-1,rt1,rt2);
        // split(rt2,r-l+1,rt2,rt3);
        // lazy(rt2)^=1;
        // merge(rt2,rt2,rt3);
        // merge(rt,rt1,rt2);
    }
    out(rt);
    return 0;
}

对于 $\tt{Splay}$，其实是差不多的，我们都是将区间转到一棵子树上进行打标记，类似于删除操作，我们将 $l-1$ 转到根，将 $r+1$ 转到根的儿子，那么 $ls(rs(rt))$ 的子树就是区间 $[l,r]$，然后和 $\tt{FHQ}$ 一样.

我的代码比较排斥 $0$，所以我干脆将整体 $+1$，最后答案 $-1$ 输出.

Splay

#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n,m;

namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,lazy,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define lazy(i) t[i].lazy
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+1;
    }
    void down(int i){
        if(!lazy(i))  return;
        lazy(i)=0;
        swap(ls(i),rs(i));
        lazy(ls(i))^=1,lazy(rs(i))^=1;
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[rs(z)==y]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            down(x);
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    int find(int k){
        if(!rt)  return 0;
        int p=rt;
        while(siz(ls(p))+1!=k){
            if(k<=siz(ls(p)))
                p=ls(p);
            else{
                k-=(siz(ls(p))+1);
                p=rs(p);
            }
            down(p);
        }
        return p;
    }
    void insert(int &i,int f,int x,int k){
        if(!i){
            i=++tot;
            siz(i)=1;fa(i)=f;val(i)=k;
            return;
        }
        if(x<=siz(ls(i))+1)  insert(ls(i),i,x,k);
        else  insert(rs(i),i,x-siz(ls(i))-1,k);
        up(i);
    }
    void out(int i){
        down(i);
        if(ls(i))  out(ls(i));
        if(val(i)>1&&val(i)<=n+1)
        write(val(i)-1),putchar(' ');
        if(rs(i))  out(rs(i));
    }
} using namespace SPLAY;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,m=read;
    insert(rt,0,1,1);
    for(int i=1;i<=n;i++){
        insert(rt,0,i+1,i+1);
        splay(tot,0);
    }
    insert(rt,0,n+2,n+2);
    int l,r;
    for(int i=1;i<=m;i++){
        l=read+1,r=read+1;
        splay(find(l-1),0);
        splay(find(r+1),rt);
        int p=ls(rs(rt));
        lazy(p)^=1;
    }
    out(rt);
    return 0;
}

$T_F$ 二逼平衡树

线段树套平衡树板子.

首先建立普通线段树，对于每个区间建一棵平衡树。
对于 $x$ 区间内排名，转化成查找区间内比它小的树的个数加 $1$，分裂求。
对于第 $k$ 小数，考虑二分，通过操作 $1$ 检查
单点修改直接从根节点跑到叶子，路过的每个节点都要删掉原数，插入新数。注意要修改原序列。
前驱后继直接分别查区间内每个小区间，取极值即可。

由于难写难调，只打了 FHQ_Treap 。

FHQ_Treap

#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 5*1e4+10;
const int inf = 2147483647;
int n,a[N],m;
int MIN=inf,MAX=-inf;

namespace FHQ_TREAP{
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N<<6];
    int tot;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    int New(int k){
        val(++tot)=k;
        siz(tot)=cnt(tot)=1;
        rd(tot)=rand();
        return tot;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)<=k)  x=i,split(rs(i),k,rs(i),y);
        else  y=i,split(ls(i),k,x,ls(i));
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int &rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    void del(int &rt,int k){
        int rt1,rt2,cut;
        split(rt,k,rt1,rt2);
        split(rt1,k-1,rt1,cut);
        merge(cut,ls(cut),rs(cut));
        merge(rt1,rt1,cut);
        merge(rt,rt1,rt2);
    }
    int sumless(int rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        int res=siz(rt1);
        merge(rt,rt1,rt2);
        return res;
    }
    int pre(int rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        if(!siz(rt1))  return -inf;
        int res=rt1;
        while(rs(res))  res=rs(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    int nxt(int rt,int k){
        int rt1,rt2;
        split(rt,k,rt1,rt2);
        if(!siz(rt2))  return inf;
        int res=rt2;
        while(ls(res))  res=ls(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    #undef ls
    #undef rs
};
using namespace FHQ_TREAP;

namespace Segment_Tree{
    struct SegTree{
        int l,r,rt;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define rt(i) tr[i].rt
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
    }tr[N<<2];
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        for(int k=l;k<=r;k++){
            insert(rt(i),a[k]);
        }
        if(l==r)  return;
        int mid=(l+r)>>1;
        build(ls(i),l,mid);
        build(rs(i),mid+1,r);
    }
    int lessk(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return sumless(rt(i),k);
        }
        int mid=(l+r)>>1,res=0;
        if(ql<=mid)  res+=lessk(ls(i),ql,qr,k);
        if(mid<qr)  res+=lessk(rs(i),ql,qr,k);
        return res;
    }
    int q_rk(int ql,int qr,int k){
        return lessk(1,ql,qr,k)+1;
    }
    int q_kth(int ql,int qr,int k){
        int st=MIN,ed=MAX,res=0;
        while(st<=ed){
            int mid=(st+ed)>>1;
            if(q_rk(ql,qr,mid)<=k)
                res=mid,st=mid+1;
            else  ed=mid-1;
        }
        return res;
    }
    void modify(int i,int x,int k){
        del(rt(i),a[x]);
        insert(rt(i),k);
        int l=l(i),r=r(i);
        if(l==r)  return;
        int mid=(l+r)>>1;
        if(x<=mid)  modify(ls(i),x,k);
        else  modify(rs(i),x,k);
    }
    int q_pre(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return pre(rt(i),k);
        }
        int mid=(l+r)>>1,res=-inf;
        if(ql<=mid) res=max(res,q_pre(ls(i),ql,qr,k));
        if(mid<qr)  res=max(res,q_pre(rs(i),ql,qr,k));
        return res;
    }
    int q_nxt(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return nxt(rt(i),k);
        }
        int mid=(l+r)>>1,res=inf;
        if(ql<=mid)  res=min(res,q_nxt(ls(i),ql,qr,k));
        if(mid<qr)   res=min(res,q_nxt(rs(i),ql,qr,k));
        return res;
    }
};
using namespace Segment_Tree;

signed main()
{
    srand(time(0));
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,m=read;
    for(int i=1;i<=n;i++)  a[i]=read,MIN=min(MIN,a[i]),MAX=max(MAX,a[i]);
    build(1,1,n);
    int op,l,r,x;
    while(m-->0){
        op=read;
        switch(op){
            case 1:
                l=read,r=read,x=read;
                write(q_rk(l,r,x)),pt;break;
            case 2:
                l=read,r=read,x=read;
                write(q_kth(l,r,x)),pt;break;
            case 3:
                l=read,x=read;//不要忘记修改原序列
                modify(1,l,x);a[l]=x;break;
            case 4:
                l=read,r=read,x=read;
                write(q_pre(1,l,r,x)),pt;break;
            case 5:
                l=read,r=read,x=read;
                write(q_nxt(1,l,r,x)),pt;break;
            default:break;
        }
    }
    return 0;
}

服了，洛谷数据太强大，我的常数也太强大，不得不写离散化。.

FHQ_Treap+离散化

#include<bits/stdc++.h>
#define getchar() getchar_unlocked()
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 5*1e4+10;
const int inf = 2147483647;
int n,a[N],m;
int MIN=inf,MAX=-inf;
int lsh[N<<1],num,tt;
int op[N];
int l[N],r[N],x[N];
int ans[N],total;

namespace FHQ_TREAP{
    struct Treap{
        int son[2],rd,cnt,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define cnt(i) t[i].cnt
        #define siz(i) t[i].siz
        #define val(i) t[i].val
    }t[N<<6];
    int tot;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+cnt(i);
    }
    int New(int k){
        val(++tot)=k;
        siz(tot)=cnt(tot)=1;
        rd(tot)=rand();
        return tot;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(val(i)<=k)  x=i,split(rs(i),k,rs(i),y);
        else  y=i,split(ls(i),k,x,ls(i));
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int &rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    void del(int &rt,int k){
        int rt1,rt2,cut;
        split(rt,k,rt1,rt2);
        split(rt1,k-1,rt1,cut);
        merge(cut,ls(cut),rs(cut));
        merge(rt1,rt1,cut);
        merge(rt,rt1,rt2);
    }
    int sumless(int rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        int res=siz(rt1);
        merge(rt,rt1,rt2);
        return res;
    }
    int pre(int rt,int k){
        int rt1,rt2;
        split(rt,k-1,rt1,rt2);
        if(!siz(rt1))  return -inf;
        int res=rt1;
        while(rs(res))  res=rs(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    int nxt(int rt,int k){
        int rt1,rt2;
        split(rt,k,rt1,rt2);
        if(!siz(rt2))  return inf;
        int res=rt2;
        while(ls(res))  res=ls(res);
        merge(rt,rt1,rt2);
        return val(res);
    }
    #undef ls
    #undef rs
};
using namespace FHQ_TREAP;

namespace Segment_Tree{
    struct SegTree{
        int l,r,rt;
        #define l(i) tr[i].l
        #define r(i) tr[i].r
        #define rt(i) tr[i].rt
        #define ls(i) (i<<1)
        #define rs(i) (i<<1|1)
    }tr[N<<2];
    void build(int i,int l,int r){
        l(i)=l,r(i)=r;
        for(int k=l;k<=r;k++){
            insert(rt(i),a[k]);
        }
        if(l==r)  return;
        int mid=(l+r)>>1;
        build(ls(i),l,mid);
        build(rs(i),mid+1,r);
    }
    int lessk(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return sumless(rt(i),k);
        }
        int mid=(l+r)>>1,res=0;
        if(ql<=mid)  res+=lessk(ls(i),ql,qr,k);
        if(mid<qr)  res+=lessk(rs(i),ql,qr,k);
        return res;
    }
    int q_rk(int ql,int qr,int k){
        return lessk(1,ql,qr,k)+1;
    }
    int q_kth(int ql,int qr,int k){
        int st=0,ed=num,res=0;
        while(st<=ed){
            int mid=(st+ed)>>1;
            if(q_rk(ql,qr,mid)<=k)
                res=mid,st=mid+1;
            else  ed=mid-1;
        }
        return res;
    }
    void modify(int i,int x,int k){
        del(rt(i),a[x]);
        insert(rt(i),k);
        int l=l(i),r=r(i);
        if(l==r)  return;
        int mid=(l+r)>>1;
        if(x<=mid)  modify(ls(i),x,k);
        else  modify(rs(i),x,k);
    }
    int q_pre(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return pre(rt(i),k);
        }
        int mid=(l+r)>>1,res=-inf;
        if(ql<=mid) res=max(res,q_pre(ls(i),ql,qr,k));
        if(mid<qr)  res=max(res,q_pre(rs(i),ql,qr,k));
        return res;
    }
    int q_nxt(int i,int ql,int qr,int k){
        int l=l(i),r=r(i);
        if(ql<=l&&r<=qr){
            return nxt(rt(i),k);
        }
        int mid=(l+r)>>1,res=inf;
        if(ql<=mid)  res=min(res,q_nxt(ls(i),ql,qr,k));
        if(mid<qr)   res=min(res,q_nxt(rs(i),ql,qr,k));
        return res;
    }
};
using namespace Segment_Tree;

void LSH(){
    sort(lsh+1,lsh+tt+1);
    num=unique(lsh+1,lsh+tt+1)-lsh-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(lsh+1,lsh+num+1,a[i])-lsh;
    }
}

signed main()
{
    srand(time(0));
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read,m=read;
    for(int i=1;i<=n;i++)  a[i]=lsh[++tt]=read;
    for(int i=1;i<=m;i++){
        op[i]=read;
        switch(op[i]){
            case 1:
                l[i]=read,r[i]=read,x[i]=read;break;
            case 2:
                l[i]=read,r[i]=read,x[i]=read;break;
            case 3:
                l[i]=read,x[i]=read;
                lsh[++tt]=x[i];break;
            case 4:
                l[i]=read,r[i]=read,x[i]=read;
                lsh[++tt]=x[i];break;
            case 5:
                l[i]=read,r[i]=read,x[i]=read;
                lsh[++tt]=x[i];break;
            default:break;
        }
    }
    LSH();
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int an;
        switch(op[i]){
            case 1:
                x[i]=lower_bound(lsh+1,lsh+num+1,x[i])-lsh;
                ans[++total]=q_rk(l[i],r[i],x[i]);break;
            case 2:
                ans[++total]=lsh[q_kth(l[i],r[i],x[i])];break;
            case 3:
                x[i]=lower_bound(lsh+1,lsh+num+1,x[i])-lsh;
                modify(1,l[i],x[i]);a[l[i]]=x[i];break;
            case 4:
                x[i]=lower_bound(lsh+1,lsh+num+1,x[i])-lsh;
                an=q_pre(1,l[i],r[i],x[i]);
                ans[++total]=(an==-inf?-inf:lsh[an]);break;
            case 5:
                x[i]=lower_bound(lsh+1,lsh+num+1,x[i])-lsh;
                an=q_nxt(1,l[i],r[i],x[i]);
                ans[++total]=(an==inf?inf:lsh[an]);break;
            default:break;
        }
    }
    for(int i=1;i<=total;i++)  write(ans[i]),pt;
    return 0;
}

$T_G$ JSOI2008火星人prefix

平衡树维护序列，$\tt{FHQ}$ 按子树大小分裂，维护 $hash$ 值，父节点存子树的 $hash$ 值，最后二分求 $LCP$。注意插入字符后要 ++n.

还是 $\tt{FHQ}$ 好打，$\tt{Splay}$ 以后再说.

FHQ_Treap

#include<bits/stdc++.h>
using namespace std;
#define  ull unsigned long long
#define read read()
#define pt puts("")
#define gc getchar
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
#define N 100010
const ull base = 233;

int n,m;
char s[N];

ull pb[N];
void init(){pb[0]=1ull;for(int i=1;i<N;i++)pb[i]=pb[i-1]*base;}

namespace FHQ_Treap{
    struct Treap{
        int son[2],rd,siz,val;
        ull hash;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define siz(i) t[i].siz
        #define val(i) t[i].val
        #define hash(i) t[i].hash
    }t[N<<1];
    int tot,rt;
    void up(int i){
        siz(i)=1+siz(ls(i))+siz(rs(i));
        hash(i)=hash(ls(i))*(pb[siz(rs(i))+1])+val(i)*pb[siz(rs(i))]+hash(rs(i));
    }
    int New(int k){
        val(++tot)=k;
        hash(tot)=k;
        siz(tot)=1;
        rd(tot)=rand();
        return tot;
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(k<=siz(ls(i)))  y=i,split(ls(i),k,x,ls(i));
        else  x=i,split(rs(i),k-(siz(ls(i))+1),rs(i),y);
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    void insert(int x,int k){
        int rt1,rt2;
        split(rt,x,rt1,rt2);
        merge(rt,rt1,New(k));
        merge(rt,rt,rt2);
    }
    void replace(int x,int k){
        int rt1,rt2,rt3;
        split(rt,x,rt1,rt2);
        split(rt1,x-1,rt1,rt3);
        merge(rt1,rt1,New(k));
        merge(rt,rt1,rt2);
    }
    ull q_hash(int l,int r){
        int rt1,rt2,rt3;
        split(rt,r,rt2,rt3);
        split(rt2,l-1,rt1,rt2);
        ull res=hash(rt2);
        merge(rt2,rt1,rt2);
        merge(rt,rt2,rt3);
        return res;
    }
} using namespace FHQ_Treap;

int solve(int l,int r){
    int st=0,ed=n-r+1;
    int res=0;
    while(st<=ed){
        int mid=(st+ed)>>1;
        if(q_hash(l,l+mid-1)==q_hash(r,r+mid-1)){
            st=mid+1;res=mid;
        }
        else  ed=mid-1;
    }
    return res;
}

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    scanf("%s",s+1);
    n=strlen(s+1);m=read;
    init();
    for(int i=1;i<=n;i++){
        insert(i-1,s[i]-'a'+1);
    }
    char op,x;
    int l,r;
    while(m-->0){
        op=gc();while(op!='Q'&&op!='R'&&op!='I')op=gc();
        switch(op){
            case 'Q':
                l=read,r=read;
                write(solve(l,r)),pt;
                break;
            case 'R':
                l=read;x=gc();while(x<'a'||x>'z')  x=gc();
                replace(l,x-'a'+1);
                break;
            case 'I':
                l=read;x=gc();while(x<'a'||x>'z')  x=gc();
                insert(l,x-'a'+1);++n;
                break;
            default:break;
        }
    }

    return 0;
}

$T_H$ 最长上升子序列

逆天性质题~~ 。

本来对于 $dp_i$ 表示以 $i$ 位置结尾的最长上升子序列长度，有

\[dp_i = \max_{1\leq j\leq i}^{a_j<a_i}dp_j + 1 \]

但是对于此题，他是按照 $1$ ~ $n$ 的顺序插入，也就是，当前插入的数，一定比原序列里所有数都大，那么。

\[dp_i = \max_{1\leq j\leq i}dp_j + 1 \]

考虑平衡树维护序列，节点存子树里的 $dp$ 最大值，直接转移即可.

对于 $\tt{FHQ}$，分裂出前 $i$ 个，$rt1$ 的 $dp$ 值 $\tt{+1}$ 即为所求
对于 $\tt{Splay}$，转到根节点，左儿子的 $dp$ 值 $\tt{+1}$ 即为所求

FHQ_Treap

#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n;

namespace FHQ_Treap{
    struct Treap{
        int son[2],rd,siz,len,ans;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define rd(i) t[i].rd
        #define siz(i) t[i].siz
        #define len(i) t[i].len
        #define ans(i) t[i].ans
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+1;
        ans(i)=max(ans(ls(i)),ans(rs(i)));
        ans(i)=max(ans(i),len(i));
    }
    void split(int i,int k,int &x,int &y){
        if(!i){x=y=0;return;}
        if(k<=siz(ls(i)))  y=i,split(ls(i),k,x,ls(i));
        else  x=i,split(rs(i),k-(siz(ls(i))+1),rs(i),y);
        up(i);
    }
    void merge(int &i,int x,int y){
        if(!x||!y){i=x|y;return;}
        if(rd(x)>rd(y))  merge(rs(x),rs(x),y),i=x;
        else  merge(ls(y),x,ls(y)),i=y;
        up(i);
    }
    int New(int k){
        ++tot;
        siz(tot)=1;
        ans(tot)=len(tot)=k;
        rd(tot)=rand();
        return tot;
    }
    void insert(int x){
        int rt1,rt2;
        split(rt,x,rt1,rt2);
        merge(rt,rt1,New(ans(rt1)+1));
        merge(rt,rt,rt2);
    }

} using namespace FHQ_Treap;

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    for(int x,i=1;i<=n;i++){
        x=read;
        insert(x);
        write(ans(rt));pt;
    }
    return 0;
}

Splay

#include<bits/stdc++.h>
using namespace std;

#define read read()
#define pt puts("")
inline int read{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x){
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  write(x/10);
    putchar(x%10+'0');
    return;
}
const int N = 1e5+10;
int n;

namespace SPLAY{
    struct Splay_Tree{
        int son[2],fa,ans,siz,val;
        #define ls(i) t[i].son[0]
        #define rs(i) t[i].son[1]
        #define ds(i) t[i].son[d]
        #define bs(i) t[i].son[d^1]
        #define fa(i) t[i].fa
        #define siz(i) t[i].siz
        #define ans(i) t[i].ans
        #define val(i) t[i].val
    }t[N];
    int tot,rt;
    void up(int i){
        siz(i)=siz(ls(i))+siz(rs(i))+1;
        ans(i)=max(ans(ls(i)),ans(rs(i)));
        ans(i)=max(ans(i),val(i));
    }
    void rotate(int x){
        int y=fa(x),z=fa(y);
        int d=(rs(y)==x);
        t[z].son[(rs(z)==y)]=x;fa(x)=z;
        ds(y)=bs(x);fa(bs(x))=y;
        bs(x)=y;fa(y)=x;
        up(y),up(x);
    }
    void splay(int x,int s){
        while(fa(x)!=s){
            int y=fa(x),z=fa(y);
            if(z!=s)
                (ls(y)==x)^(ls(z)==y)?rotate(x):rotate(y);
            rotate(x);
        }
        if(!s)  rt=x;
    }
    void find(int x){
        if(!rt)  return;
        int p=rt;
        while(siz(ls(p))+1!=x){
            if(x<=siz(ls(p))+1){
                p=ls(p);
            }
            else{
                x-=(siz(ls(p))+1);
                p=rs(p);
            }
        }
        splay(p,0);
    }
    void insert(int &i,int f,int x,int k){
        if(!i){
            i=++tot;
            fa(i)=f;
            siz(i)=1;
            ans(i)=val(i)=k;
            return;
        }
        if(x<=siz(ls(i))+1)  insert(ls(i),i,x,k);
        else  insert(rs(i),i,x-siz(ls(i))-1,k);
        up(i);
    }
    
} using namespace SPLAY;


signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("lty.in","r",stdin);
        freopen("lty.out","w",stdout);
    #endif
    n=read;
    for(int x,k,i=1;i<=n;i++){
        x=read;
        if(!x)  k=1;
        else if(x==i-1)  k=ans(rt)+1;
        else{
            find(x+1);
            k=ans(ls(rt))+1;
        }
        insert(rt,0,x+1,k);
        splay(tot,0);
        write(ans(rt));pt;
    }
    return 0;
}

$T_I$ 星系探索

好像是阉割版的 $\tt{ETT/LCT}$(Wang54321说的)，不会.

伍.闲话

转眼间在奥赛班的短短 $3$ 个月只剩最后几天，整个下午跑机房，还能有多长时间。。。$3$ 个月说长不长说短不短，学到了不少东西，虽然不像别的奥赛对高中文化课有很大帮助，但是

我们学的东西是他们这辈子都不一定能接触到的。。.

不知道回原班在中考前还能学多长时间 $\tt{OI}$，像小 $\tt{H}$ 说的。

也不知道回原班之后的二三十天，自己还能在这个机位上坐几个小时。这种感觉，或有点像心有余而力不足而被迫退役的感觉吧。当然我也希望，两年后的自己，不会有这种感觉。——$\tt{HANGRY\_ Sol}$ 。

没想到二模完没有立刻【垃圾分类】，那就把 $\tt{Splay}$ 收尾，不用放假加班了，珍惜机房的每一分钟吧... 。

最后此篇关于平衡树Treap&Splay[学习笔记]的文章就讲到这里了,如果你想了解更多关于平衡树Treap&Splay[学习笔记]的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐： 05_不同路径2(带障碍物版)

文章推荐：连网安装mysql与源码安装mysql

文章推荐： WindowsServer2022初始设置

平衡树Treap&Splay[学习笔记]
平衡树 $\tt{Treap}$ & $\tt{Splay}$ 壹.单旋 $\tt{Treap}$ 首先了解 $\tt{BST}$ 非常好用的东西，但是数据可以把它卡成一
algorithm - splay 树中值的范围函数？
我是数据结构的初学者。我正在尝试为带有 splay 树的范围函数编写一些伪代码:Range(S, A, B)，它将 S 更改为其键值 C 满足 A ≤ 的所有成员的集合C ≤ B。我知道伸展树(Spl
algorithm - Splay 树最坏情况搜索时间
由于 splay tree 是一种不平衡二叉搜索树 ( brilliant.org/wiki/splay-tree )，它不能保证最大为 O(log(n)) 的高度。因此，我认为它不能保证 O(log
algorithm - Splay Trees中节点的插入和删除
我有 2 个关于八角树的问题: 1。删除节点我正在使用的书是这样说的:''当删除键 k 时，我们展开被删除的节点 w 的父节点。删除 8 的示例: 但是，我正在做的是:如果删除的节点不是根节点，我展
java - 空指针伸展树(Splay Tree)
我正在研究伸展树(Splay Tree)的右旋转方法。当我尝试运行程序时，我不断收到空指针异常，但我不确定为什么。这是我的树 5 / 2 / 1 这是我得到空指
c++ - 我的 splay 树实现中的奇怪错误
我正在尝试为伸展树(Splay Tree)编写 C++ 模板结构，但是当我尝试测试代码时，我得到了非常奇怪的结果。这是我的模板代码: template struct splaytree {
algorithm - 什么是 splay 树中的摊销复杂性？
我试图了解摊销的复杂性并在网上进行了几次搜索，但我还找不到好的资源。那么谁能解释一下什么是摊销复杂度以及它如何在 splay 树中每个操作变为 O(lg n)？最佳答案对伸展树(Splay Tr
algorithm - 无法弄清楚 splaying 是如何工作的
我不明白展开是如何工作的。我无法理解的部分是我们如何知道 a: i) zig ii) zig-zag 或 iii) zig-zig 必须完成。如果我理解正确的话，这与路径中的当前节点有关。如果它
algorithm - Splay tree 现实生活中的应用
您会在生产环境中的哪些地方使用 splay-tree。我指的是真实生活的例子。我正在考虑使用尝试和拉伸(stretch)树实现自动完成。对于大型数据集，从节点 x 到叶子遍历 trie 以返回结果并
algorithm - 递归伸展树(Splay Tree)
我正在尝试自下而上地实现递归伸展树(Splay Tree)。我向下递归到需要展开的节点，然后找到该节点的父节点和祖父节点。然后，我可以根据情况进行之字形或之字形。问题是完成后，我将已经张开一次的节点返
algorithm - 比较 splay 树效率的最佳方法是什么？
我已经实现了几个 splay tree算法。比较它们的最佳方式是什么？添加随机节点时比较执行时间是否是一个好的开始？我还实现了一个二叉搜索树，用于跟踪每个节点的访问量。我编写了一个 optimi
algorithm - 我可以使用递归算法来实现 Splay 树吗？
我一直在研究 Splay 树，因为我想实现一个。目前，我对红黑树、AVL 树、跳表和其他更简单的数据结构有一些“自学”经验。我想实现我的第一个 splay 树，但如果可能的话，我想要一个递归实现(我喜
algorithm - 伸展树(Splay Tree)的摊销分析
展开树插入/删除可以用不同的方式完成。一种流行的方法是插入 key 并将其展开到根。但是我读过还有一种不同的方法，这个想法是拆分它分成两棵树，左边的树有值插入键。备用删除方法也是如此，将要删除的键
data-structures - 与哈希表相比，splay 树有哪些优势？
由于 splay 树用于缓存，我想知道当我想有效缓存时，Splay Tree 比 HashTable 有什么优势？我什么时候应该更喜欢 splay 树而不是哈希表？我想这是一个比 BST 更专业的
eclipse - 在eclipse软件包浏览器中，如何单击一下即可伸展树(Splay Tree)？
例如，我有一个这样的文件夹结构: src └─test ├─java └─com └─google └─test
javascript - 如何在单击或双击父元素时伸展树(Splay Tree)列表的子节点？
问题是，当我单击树列表父元素时，它不会像在树面板中的 DoubleClick 上展开那样展开。任何人都可以帮助我找到我应该做什么来实现这一目标？在这张图片中，当我单击父节点时，它不会像我们看到的那样展
javascript - 单击箭头或其他图标以伸展树(Splay Tree)的分支时会触发什么事件？
我知道如何捕获节点上的点击: // Define action when a node was clicked. $('#mytree').on("select_node.jstree
Puppet splay 和 splaylimit 解释了吗？
我正在寻找有人解释 Puppet 配置中 splay 和 splaylimit 的用法。 Puppet 站点本身的文档至少可以说是有限的。我正遭受主控上的惊群攻击，即多个代理同时向该代理敲击其目录，直
java - 自动调整伸展树(Splay Tree)的旋转策略
我必须使用java实现伸展树(Splay Tree)结构。给定一个名为 Node 的类，它具有: 左、右 child 信息(整数) 节点的高度我的作业包括创建“插入”方法。我已经尝试了一些策略，但
java - 伸展树(Splay Tree)搜索实现
我一直在尝试学习一些数据结构的细节，并且我正在尝试让二叉伸展树(Splay Tree)正常工作。每次我运行以下代码并且我正在寻找的节点超过根的节点时，它都会告诉我它在那里，然后只删除从根向下的整个一侧

撒哈拉

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

平衡树Treap&Splay[学习笔记]

平衡树 \(\tt{Treap}\) & \(\tt{Splay}\)

壹.单旋 \(\tt{Treap}\)

贰.无旋 \(\tt{FHQ\ Treap}\)

叁.双旋 \(\tt{Splay}\)

肆.\(hs\)题单

\(T_D\) 普通平衡树

\(T_A\) 营业额统计

\(T_B\) 宠物收养所

\(T_C\) 郁闷的出纳员

\(T_E\) 文艺平衡树

\(T_F\) 二逼平衡树

\(T_G\) JSOI2008火星人prefix

\(T_H\) 最长上升子序列

\(T_I\) 星系探索

伍.闲话