浅析 FHQ-Treap&Treap&可持久化平衡树&树套树

ingo_dtw · 2026-01-09 23:02:00 · 算法·理论

前言

会做模板题我们只知道在平衡树上加一个值和查询平衡树上某个元素排名第几，排名第几的元素是什么，在实际使用过程中你发现这些功能并不是很常用。

这个时候，我们需要维护的不再是元素本身的值，而是一个序列，也就是说我们插入不再是使用一个元素的值作为插到哪的根据，而是使用元素的下标。此外，我们还需要注意我们进行分裂/合并的时候也不是使用元素的值而是子树大小。

P4036 [JSOI2008] 火星人

题意很简单，求一段后缀与一段后缀的 LCQ 不难注意到，如果没有修改操作，我们完全可以对原字符串 hash 然后使用二分求出，但是这里需要插入和修改操作，使得我们需要使用平衡树 \mathcal{O}(n\log^2n) 解决。 :::success[Ac Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long 
#define ull unsigned long long
#define R register
#define rint register int
#define _ read()
inline bool blank(const char &x)
{
    return !(x^13)||!(x^32)||!(x^10)||!(x^9);
}
inline int read()
{
    rint r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
const int N=5e5+10,B=131;
ull b[N];
char c[N];
mt19937 rnd(1);
struct FHQ_Treap
{
    int root=0,cnt=0,len=0;ull cc[N];
    struct node
    {
        int l,r,s,siz;ull h;
    }tr[N];
    inline int neo(char x)
    {
        tr[++cnt]={0,0,(int)(rnd()),1,(ull)(x)};
        cc[cnt]=x;
        return cnt;
    }
    inline void pushup(rint u)
    {
        if(!u) return;
        tr[u].siz=tr[tr[u].l].siz+tr[tr[u].r].siz+1;
        tr[u].h=tr[tr[u].l].h*b[tr[tr[u].r].siz+1] + b[tr[tr[u].r].siz]*cc[u] + tr[tr[u].r].h;
    }
    inline pair<int,int> split(rint u,rint k)
    {
        if(!u) return {0,0};
        if(tr[tr[u].l].siz+1<=k)
        {
            auto x=split(tr[u].r,k-(tr[tr[u].l].siz+1));
            tr[u].r=x.first;
            pushup(u);            
            return {u,x.second};
        }
        else
        {
            auto x=split(tr[u].l,k);
            tr[u].l=x.second;
            pushup(u);
            return {x.first,u};
        }
    }
    inline int merge(rint l,rint r)
    {
        if(!l||!r) return l|r;
        if(tr[l].s<tr[r].s)
        {
            tr[l].r=merge(tr[l].r,r);
            pushup(l);
            return l;
        }
        else
        {
            tr[r].l=merge(l,tr[r].l);
            pushup(r);
            return r;
        }
    }
    inline void insert(rint p,char x)
    {
        auto [l,r]=split(root,p);++len;
        root=merge(merge(l,neo(x)),r);
    }
    inline void modify(rint p,char x)
    {
        auto [l,r]=split(root,p-1);
        auto [mid,rr]=split(r,1);
        tr[mid].h=cc[mid]=x;
        root=merge(merge(l,mid),rr);
    }
    inline ull query(rint ql,rint qr)
    {
        if(ql>qr) return 0;
        auto [l,midr]=split(root,ql-1);
        auto [mid,r]=split(midr,qr-ql+1);
        ull ans=tr[mid].h;
        root=merge(merge(l,mid),r);
        return ans;
    }

}tr;
signed main() 
{  
    memset(tr.tr,0,sizeof(tr.tr));
    scanf("%s",c+1);
    b[0]=1;
    for(rint i=1;i<N;++i) b[i]=b[i-1]*B;
    for(rint i=1;c[i];++i)
    {
        tr.insert(i-1,c[i]);

    }
    ull p=0;    
    // auto [lp,midr]=tr.split(tr.root,3-1);
    // cout<<midr<<' ';
    // auto [mid,rp]=tr.split(midr,1);
    // cout<<mid<<' ';
    // cout<<tr.tr[mid].h<<endl;
    // for(rint i=3;c[i];++i) cout<<tr.query(i,i)<<endl;
    // cout<<endl;
    rint q=_;
    while(q--)
    {
        char op;read(op);
        if(op=='Q')
        {
            rint x=_,y=_;
            rint l=0,r=tr.len-max(x,y)+1,mid,ans=0;
            while(l<=r)
            {
                mid=l+r>>1;
                if(tr.query(x,x+mid-1)==tr.query(y,y+mid-1)) ans=mid,l=mid+1;
                else r=mid-1;
            }
            out(ans);pc('\n');
        }
        else if(op=='R')
        {
            rint x=_;char y;read(y);
            tr.modify(x,y);
        }
        else
        {
            rint x=_;char y;read(y);tr.insert(x,y);
        }
    }
    return 0; 
} 
//我也要写吗

:::

P3391 【模板】文艺平衡树

考虑每次翻转的时候把需要翻转的区间切出来，然后对于这个节点打上类似于线段树的懒标记，每次分裂/合并前下传即可。 :::success[Ac Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long 
#define ull unsigned long long
#define R register
#define rint register int
#define _ read()
inline bool blank(const char &x)
{
    return !(x^13)||!(x^32)||!(x^10)||!(x^9);
}
inline int read()
{
    rint r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
const int N=1e5+10;
mt19937 rnd(time(0));
struct FHQ_Treap
{
    int root,cnt;
    struct node
    {
        int l,r,s,x,siz;bool set;
    }tr[N];
    inline int neo(rint v)
    {
        tr[++cnt]={0,0,(int)(rnd()),v,1,0};
        return cnt;
    }
    inline void pushup(rint u)
    {
        tr[u].siz=tr[tr[u].l].siz+1+tr[tr[u].r].siz;
    }
    inline void pushdown(rint u)
    {
        if(tr[u].set)
        {
            swap(tr[u].l,tr[u].r);
            if(tr[u].l) tr[tr[u].l].set^=1;
            if(tr[u].r) tr[tr[u].r].set^=1;
            tr[u].set=0;
        }
    }
    inline pair<int,int>split(rint u,rint k)
    {
        if(!u) return {0,0};
        pushdown(u);
        if(tr[tr[u].l].siz+1<=k)
        {
            auto x=split(tr[u].r,k-(tr[tr[u].l].siz+1));
            tr[u].r=x.first;
            pushup(u);
            return {u,x.second};
        }
        else
        {  
            auto x=split(tr[u].l,k);
            tr[u].l=x.second;
            pushup(u);
            return {x.first,u};
        }
    }
    inline int merge(rint l,rint r)
    {
        if(!l||!r) return l|r;
        if(tr[l].s<tr[r].s)
        {
            pushdown(l);
            tr[l].r=merge(tr[l].r,r);
            pushup(l);
            return l;
        }
        else
        {
            pushdown(r);
            tr[r].l=merge(l,tr[r].l);
            pushup(r);
            return r;
        }
    }
    inline void insert(rint v)
    {
        root=merge(root,neo(v));
    }
    inline void modify(rint ql,rint qr)
    {
        auto [l,midr]=split(root,ql-1);
        auto [mid,r]=split(midr,qr-ql+1);
        tr[mid].set^=1;
        root=merge(merge(l,mid),r);
    }
    inline int query(rint k)
    {
        auto [l,rmid]=split(root,k-1);
        auto [mid,r]=split(rmid,1);
        rint ans=tr[mid].x;
        root=merge(merge(l,mid),r);
        return ans;
    }
}tr;
signed main() 
{  
    rint n=_,q=_;
    for(rint i=1;i<=n;++i) tr.insert(i);
    while(q--)
    {
        rint l=_,r=_;tr.modify(l,r);
    }
    for(rint i=1;i<=n;++i)
    {
        out(tr.query(i));pc(' ');
    }
    return 0; 
} 
//我也要写吗

:::

\texttt{FHQ-Treap} 上启发式合并

P3224 [HNOI2012] 永无乡

显然，对于这个题我们不妨考虑对于每个节点都建立一颗 \texttt{FHQ-Treap}，一但连接直接合并即可，然后查询也是用并查集处理一下即可。

但是如果我们合并两颗 \texttt{FHQ-Treap} 显然不能直接去用 merge 合，因为没有一颗 \texttt{FHQ-Treap} 的全部节点一定小于另一颗这种性质。

既然是启发式合并，我们肯定要把一颗节点少的 \texttt{FHQ-Treap} 合到另一颗去，这个时候你猜我会怎么做？

没错！我们直接聪明的把小的 \texttt{FHQ-Treap} 遍历，然后插入到大的里面！ :::success[Ac Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long 
#define ull unsigned long long
// #define R register
#define rint register int
#define _ read<int>()
inline bool blank(const char &x)
{
    return !(x^13)||!(x^32)||!(x^10)||!(x^9);
}
template<class T>inline T read()
{
    T r=0,f=1;char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
const int N=4e5+10;
int f[N];
mt19937 rnd(time(0));
struct FHQ_Treap
{
    int cnt;
    struct Node
    {
        int l,r,x,pri,siz,id;
    }tr[N];
    inline void pushup(rint u)
    {
        tr[u].siz=tr[tr[u].l].siz+1+tr[tr[u].r].siz;
    }
    inline int neo(rint id,rint x)
    {
        tr[++cnt]={0,0,x,(int)rnd(),1,id};
        return cnt;
    }
    inline pair<int,int> split(rint u,rint k)
    {
        if(!u) return {0,0};
        if(tr[u].x<k)
        {
            auto x=split(tr[u].r,k);
            tr[u].r=x.first;
            pushup(u);
            return {u,x.second};
        }
        else
        {
            auto x=split(tr[u].l,k);
            tr[u].l=x.second;
            pushup(u);
            return {x.first,u};
        }
    }
    inline int merge(rint u,rint v)
    {
        if(!u||!v) return u|v;
        if(tr[u].pri<tr[v].pri)
        {
            tr[u].r=merge(tr[u].r,v);
            pushup(u);
            return u;
        }
        else
        {
            tr[v].l=merge(u,tr[v].l);
            pushup(v);
            return v;
        }
    }
    inline int find(rint k,rint rt)
    {
        rint u=rt;
        while(u)
        {
            if(tr[tr[u].l].siz+1==k) return tr[u].id;
            if(tr[tr[u].l].siz>=k) u=tr[u].l;
            else k-=(tr[tr[u].l].siz+1),u=tr[u].r;
        }
        return -1;
    }
    inline void dfs(rint &u,rint v)
    {
        if(!v) return;
        rint ls=tr[v].l,rs=tr[v].r;
        dfs(u,ls);
        dfs(u,rs);
        auto [l,r]=split(u,tr[v].x);
        tr[v]={0,0,tr[v].x,tr[v].pri,1,tr[v].id};
        u=merge(merge(l,v),r);
    }
    inline int Merge(rint u,rint v)
    {
        if(!u||!v) return u|v;
        if(tr[u].siz<tr[v].siz) swap(u,v);
        dfs(u,v); 
        return u;   
    }
}tr;
inline int find(rint x)
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
signed main() 
{  
    rint n=_,m=_;
    for(rint i=1;i<=n;++i) tr.neo(i,_),f[i]=i;
    for(rint i=1;i<=m;++i)
    {
        rint u=_,v=_;
        rint fu=find(u),fv=find(v);
        if(fu==fv) continue;
        rint tmp=tr.Merge(fu,fv);
        f[fu]=f[fv]=f[tmp]=tmp;
    }
    rint q=_;
    while(q--)
    {
        char op;read(op);
        if(op=='Q') 
        {
            rint x=_,k=_;
            out(tr.find(k,find(x)));pc('\n');
        }
        else
        {
            rint u=_,v=_;
            rint fu=find(u),fv=find(v);
            if(fu==fv) continue;
            rint tmp=tr.Merge(fu,fv);
            f[fu]=f[fv]=f[tmp]=tmp;
        }
    }
    return 0;   
} 
//我也要写吗

:::

P1552 [APIO2012] 派遣

读完题不难注意到，如果没有这些子树限制的化，我们完全可以二分求出答案，所以我们事实上可以先从给定树的叶子结点开始计算答案然后到后面的节点，我们可以先启发式合并其子结点的平衡树，然后递归求解答案即可。

:::success[Ac Code]

#include <bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long
#define _ read<int>()
#define R register
#define rint register int
template<class T>inline T read()
{
    T r=0,f=1; char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
mt19937 rnd(time(0));

const int N=1e5+10;
int n,m,p[N],ans; 
vector<vector<int>>g;
struct FHQ_Treap
{
    int cnt;
    struct Node
    {
        int l,r,siz,pri,s,x;
    }tr[N];
    inline int neo(rint x)
    {
        tr[++cnt]={0,0,1,(int)rnd(),x,x};
        return cnt;
    }
    inline void pushup(rint u)
    {
        tr[u].siz=tr[tr[u].l].siz+1+tr[tr[u].r].siz;
        tr[u].s=tr[tr[u].l].s+tr[tr[u].r].s+tr[u].x;
    }
    inline pair<int,int> split(rint u,rint k)
    {
        if(!u) return {0,0};
        if(tr[u].x<k)
        {
            auto x=split(tr[u].r,k);
            tr[u].r=x.first;
            pushup(u);
            return {u,x.second};
        }
        else
        {
            auto x=split(tr[u].l,k);
            tr[u].l=x.second;
            pushup(u);
            return {x.first,u};
        }
    }
    inline int merge(rint u,rint v)
    {
        if(!u||!v) return u|v;
        if(tr[u].pri<tr[v].pri)
        {
            tr[u].r=merge(tr[u].r,v);
            pushup(u);
            return u;
        }
        else
        {
            tr[v].l=merge(u,tr[v].l);
            pushup(v);
            return v;
        }
    }
    inline void dfs(rint &u,rint v)
    {
        if(!v) return ;
        dfs(u,tr[v].l);
        dfs(u,tr[v].r);
        tr[v]={0,0,1,tr[v].pri,tr[v].x,tr[v].x};
        auto [l,r]=split(u,tr[v].x);
        u=merge(merge(l,v),r);
    }
    inline int Merge(rint u,rint v)
    {
        if(!u||!v) return u|v;
        if(tr[u].siz<tr[v].siz) swap(u,v);
        dfs(u,v);
        return u;
    }
    inline int query(rint rt,rint k)
    {
        rint u=rt;
        while(u)
        {
            if(tr[tr[u].l].siz+1==k) return tr[u].x;

            if(tr[tr[u].l].siz>=k) u=tr[u].l;
            else k-=(tr[tr[u].l].siz+1),u=tr[u].r;
        }
        return -1;
    }
    inline int query1(rint rt,rint k)
    {
        auto [l,r]=split(rt,k+1);
        rint ans=tr[l].s;
        rt=merge(l,r);
        return ans;
    }
}tr;
inline int dfs(rint u)
{
    if(!u) return 0;
    rint rt=-1;
    for(int v:g[u])
    {
        if(rt!=-1) rt=tr.Merge(rt,dfs(v));
        else rt=dfs(v);
    }  
    if(rt==-1) rt=u;
    else rt=tr.Merge(rt,u);
    rint l=0,r=tr.tr[rt].siz,mid,anss=0;
    while(l<=r)
    {
        mid=l+r>>1;
        rint s=tr.query1(rt,tr.query(rt,mid));
        if(s<=m)
        {
            anss=mid;l=mid+1;
        }
        else r=mid-1;
    }
    // cerr<<u<<' '<<anss<<' '<<p[u]<<' '<<tr.query(rt,1)<<endl;
    ans=max(ans,anss*p[u]);
    return rt;
}
signed main()
{   
    n=_,m=_; g.resize(n+1);

    rint rt;
    for(rint i=1;i<=n;++i)
    {   
        rint u=_,x=_;p[i]=_;
        if(u) g[u].push_back(i);
        else rt=i;
        tr.neo(x);
    }   
    dfs(rt);
    out(ans);
    return 0;

}   

:::

注意启发式合并和二分的时间复杂度不是合在一起的，所以时间复杂度 \mathcal{O}(n \log^2 n)。

动态分裂 \texttt{FHQ-Treap}

当节点数来到 10^8 甚至更大的时候，我们是不可能去把这些节点全都开下来的。

这个时候，我们不妨先设置一个大节点比如说开始就包含一个区间 [l,r]，当我们需要对于 v 这个节点操作的时候，我们不妨直接把 [l,r] 分裂为 [l,v-1]，[v,v],[v+1,r]。

同样的，对于查询排名，我们不妨对于每个节点记录一个 fa，在查询这个区间的排名时，我们可以直接往上跳，当这个节点为其父亲节点的右子节点时，我们就可以加上父节点的左子子树的贡献和父亲节点本身的贡献，特别的，在分裂的时候需要注意分裂完后父亲节点的变化。

P3285 [SCOI2014] 方伯伯的OJ

因为数据范围 n\le 10^8 所以我们考虑动态分裂一下，但是你不难发现啊，这个什么题目会改变编号的，此时我们不妨再开个平衡树，T_l 表示一个节点，这个节点所属的区间是 [l,r] 而且我们不关心这个 r。

其他的其实比较简单，我们来看看怎么把 [v,v] 这个节点分裂出来：

首先，我们需要找到一个包含 v 的区间，我们可以在 T 里找到一个左端点大于 v 的，那么这个节点的前一个就是左端点小于等于 v 的，接着，我们在平衡树内找到代表此区间的节点，把这个节点删掉，然后创建三个分别代表 [l,v-1],[v,v],[v+1,r] 的节点合并进去，最后修改一下 T。

特别的，之前的文艺平衡树内我们每个节点的大小是 1 但是此题，我们的大小为 r-l+1。

如果还是不理解，不妨看看代码。

:::success[Ac Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
// #define int long long 
#define ull unsigned long long
// #define R register
#define rint register int
#define _ read<int>()
inline bool blank(const char &x)
{
    return !(x^13)||!(x^32)||!(x^10)||!(x^9);
}
template<class T>inline T read()
{
    T r=0,f=1;char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
inline void read(string &x) 
{
    x="";char a=gc(); 
    for(;blank(a)&&(a^-1);a=gc()); 
    for(;!blank(a)&&(a^-1);a=gc()) x+=a;
}
const int N=1e5+10;
mt19937 rnd(time(0));
struct FHQ_Treap
{
    int cnt,sta[N],top,root;
    struct Node
    {
        int ls,rs,pri,siz,l,r,fa;
    }tr[N<<2];
    map<int,int>mp;
    inline int neo(rint l,rint r)
    {
        rint u=top?sta[top--]:++cnt;
        tr[u]={0,0,(int)rnd(),r-l+1,l,r,0};
        return u;
    }
    inline void pushup(rint u)
    {
        tr[u].siz=tr[tr[u].ls].siz+(tr[u].r-tr[u].l+1)+tr[tr[u].rs].siz;
        if(tr[u].ls) tr[tr[u].ls].fa=u;
        if(tr[u].rs) tr[tr[u].rs].fa=u;
    }
    inline pair<int,int> split(rint u,rint k)
    {
        if(!u) return {0,0};
        if(tr[tr[u].ls].siz+(tr[u].r-tr[u].l+1)<=k)
        {
            auto x=split(tr[u].rs,k-(tr[tr[u].ls].siz+(tr[u].r-tr[u].l+1)));
            tr[u].rs=x.first;
            pushup(u);
            tr[x.second].fa=0;
            return {u,x.second};
        }
        else
        {
            auto x=split(tr[u].ls,k);
            tr[u].ls=x.second;
            pushup(u);
            tr[x.first].fa=0;
            return {x.first,u};
        }
    }
    inline int merge(rint u,rint v)
    {
        if(!u||!v) return u|v;
        if(tr[u].pri<tr[v].pri)
        {
            tr[u].rs=merge(tr[u].rs,v);
            pushup(u);
            return u;
        }
        else
        {
            tr[v].ls=merge(u,tr[v].ls);
            pushup(v);
            return v;
        }
    }
    inline int kth(rint u)
    {
        rint ans=tr[tr[u].ls].siz+1;
        while(u)
        {
            rint p=tr[u].fa;
            if(p&&tr[p].rs==u) ans+=(tr[tr[p].ls].siz+(tr[p].r-tr[p].l+1));
            u=p;
        }
        return ans;
    }
    inline int sid(rint v)
    {
        auto it=mp.upper_bound(v);
        --it;
        rint u=it->second;
        rint l=tr[u].l,r=tr[u].r;
        if(l==r) return u;
        rint rk=kth(u);//[rk,rk+r-l]
        auto [L,midr]=split(root,rk-1);
        auto [mid,R]=split(midr,r-l+1);
        mp.erase(l);
        rint x=0,y=0,z=0;
        if(l<v) x=neo(l,v-1),mp[l]=x;
        y=neo(v,v),mp[v]=y;
        if(r>v) z=neo(v+1,r),mp[v+1]=z;
        sta[++top]=mid;
        root=merge(L,merge(merge(x,merge(y,z)),R));
        return y;
    }
    inline int modify(rint x,rint y)
    {
        rint u=sid(x);
        rint rk=kth(u);
        mp.erase(tr[u].l);
        tr[u].l=tr[u].r=y;  
        mp[y]=u;
        return rk;
    }
    inline int fth(rint x) 
    {
        rint u=sid(x);
        rint ans=kth(u);
        auto [l,midr]=split(root,ans-1);
        auto [mid,r]=split(midr,1);
        root=merge(mid,merge(l,r));
        return ans;
    }
    inline int eth(rint x)
    {
        rint u=sid(x);
        rint ans=kth(u);
        auto [l,midr]=split(root,ans-1);
        auto [mid,r]=split(midr,1);
        root=merge(merge(l,r),mid);
        return ans;
    }
    inline int kkth(rint k)
    {
        rint u=root;
        while(u)
        {
            if(tr[tr[u].ls].siz+1<=k&&k<=tr[tr[u].ls].siz+(tr[u].r-tr[u].l+1)) return tr[u].l+(k-tr[tr[u].ls].siz-1);
            if(tr[tr[u].ls].siz>=k) u=tr[u].ls;
            else
            {
                k-=(tr[tr[u].ls].siz+(tr[u].r-tr[u].l+1));
                u=tr[u].rs;
            }
        }
        return -1;
    }
}tr;
signed main() 
{  
    rint n=_,q=_;
    tr.root=tr.neo(1,n);
    tr.mp[1]=tr.root;
    rint a=0;
    while(q--)
    {
        rint op=_,x=_-a;
        if(op==1)
        {
            rint y=_-a;
            out(a=tr.modify(x,y));pc('\n');
        }
        else if(op==2)
        {
            out(a=tr.fth(x));pc('\n');
        }
        else if(op==3)
        {
            out(a=tr.eth(x));pc('\n');
        }
        else 
        {
            out(a=tr.kkth(x));pc('\n');
        }

    }
    return 0;   
} 
//穗穗平安～

:::

线段树套 \texttt{FHQ-Treap}

P3380 【模板】树套树

如题意，我们不难发现，如果把限制区间给去掉，我们事实上是很容易去用平衡树做的，但是如果加上区间限制，就很困难了。

那么我们回想一个非常有用的数据结构，即标题的线段树，我们不妨考虑将每个询问拆解为一个个区间，然后考虑对于每一个区间都开一个 \texttt{FHQ-Treap}。

通俗一点来说，我们不妨对于线段树上每一个节点管辖的区间建立一颗 \texttt{FHQ-Treap}，然后这个 \texttt{FHQ-Treap} 内的节点就是这个区间内的节点。

然后你不难发现，对于所有的询问与修改就可做了。

特别的，对于询问 2 我们不妨直接二分这个值，然后就可以 \mathcal{O}(\log^3 n) 做了。

时间复杂度：\mathcal{O}(m \log^3 n)。

:::success[Ac Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
// #define int long long 
#define ull unsigned long long
// #define R register
#define rint register int
#define _ read<int>()
inline bool blank(const char &x)
{
    return !(x^13)||!(x^32)||!(x^10)||!(x^9);
}
template<class T>inline T read()
{
    T r=0,f=1;char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
inline void read(string &x) 
{
    x="";char a=gc(); 
    for(;blank(a)&&(a^-1);a=gc()); 
    for(;!blank(a)&&(a^-1);a=gc()) x+=a;
}
const int M=2e7+10,N=2e5+10;
struct Node
{ 
    int l,r,siz,pri,x;
}tr[M];
int cnt,a[N],n;
mt19937 rnd(time(0));
struct FHQ_Treap
{
    int root;

    inline int neo(rint x)
    {
        tr[++cnt]={0,0,1,(int)rnd(),x};
        return cnt;
    }
    inline void pushup(rint u)
    {
        tr[u].siz=tr[tr[u].l].siz+1+tr[tr[u].r].siz;
    }
    inline pair<int,int> split(rint u,rint k)
    {
        if(!u) return {0,0};
        if(tr[u].x<=k)
        {
            auto x=split(tr[u].r,k);
            tr[u].r=x.first;
            pushup(u);
            return {u,x.second};
        }
        else
        {
            auto x=split(tr[u].l,k);
            tr[u].l=x.second;
            pushup(u);
            return {x.first,u};
        }
    }
    inline int merge(rint u,rint v)
    {
        if(!u||!v) return u|v;
        if(tr[u].pri<tr[v].pri)
        {
            tr[u].r=merge(tr[u].r,v);
            pushup(u);
            return u;
        }
        else
        {
            tr[v].l=merge(u,tr[v].l);
            pushup(v);
            return v;
        }
    }
    inline int kkth(rint k,rint py)
    {
        auto [l,r]=split(root,k-1);
        rint ans=tr[l].siz;
        root=merge(l,r);
        return ans+py;
    }
    inline int kth(rint k)
    {
        rint pos=root;
        while(pos)
        {
            if(k==tr[tr[pos].l].siz+1) return tr[pos].x;

            if(k<=tr[tr[pos].l].siz) pos=tr[pos].l;
            else 
            {
                k-=(tr[tr[pos].l].siz+1);
                pos=tr[pos].r;
            }
        }
    }
    inline int pre(rint x)
    {
        auto [l,r]=split(root,x-1);
        rint ans=0;
        if(!l) ans=-2147483647;
        else
        {
            rint u=l;
            while(tr[u].r) u=tr[u].r;
            ans=tr[u].x;
        }
        root=merge(l,r);
        return ans;
    }
    inline int nxt(rint x)
    {
        auto [l,r]=split(root,x);
        rint ans=0;
        if(!r) ans=2147483647;
        else
        {
            rint u=r;
            while(tr[u].l) u=tr[u].l;
            ans=tr[u].x;
        }
        root=merge(l,r);
        return ans;
    }
    inline void ins(rint x)
    {
        auto [l,r]=split(root,x-1);
        root=merge(merge(l,neo(x)),r);
    }
    inline void del(rint x)
    {
        auto [l,midr]=split(root,x-1);
        auto [mid,r]=split(midr,x);
        mid=merge(tr[mid].l,tr[mid].r);
        root=merge(merge(l,mid),r);
    }
    inline void build(rint l,rint r)
    {
        for(rint i=l;i<=r;++i) ins(a[i]);
    }
}trr[N<<2];
struct Segment_Tree
{
    inline void build(rint u,rint l,rint r)
    {
        trr[u].build(l,r);
        if(l==r) return ;
        rint mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
    inline int query1(rint u,rint L,rint R,rint l,rint r,rint k)
    {
        if(L<=l&&r<=R)
        {
            return trr[u].kkth(k,0);
        }
        rint mid=l+r>>1,ans=0;
        if(L<=mid) ans+=query1(u<<1,L,R,l,mid,k);
        if(R>mid) ans+=query1(u<<1|1,L,R,mid+1,r,k);
        return ans;
    }
    inline int query2(rint u,rint ql,rint qr,rint k) 
    {
        rint l=0,r=1e8+10,mid,ans;
        while(l<=r)
        {
            mid=l+r>>1;
            if(query1(1,ql,qr,1,n,mid)+1<=k)
            {
                l=mid+1;ans=mid;
            }
            else r=mid-1;
        }
        return ans;
    }
    inline void modify(rint u,rint p,rint v,rint l,rint r)
    {   
        if(l<=p&&p<=r)
        {
            trr[u].del(a[p]);
            trr[u].ins(v);
        }
        if(l==r) return;
        rint mid=l+r>>1;
        if(p<=mid) modify(u<<1,p,v,l,mid);
        else modify(u<<1|1,p,v,mid+1,r);
    }
    inline int pre(rint u,rint x,rint L,rint R,rint l,rint r)
    {
        if(L<=l&&r<=R)
        {
            return trr[u].pre(x);
        }
        rint mid=l+r>>1,ans=-2147483647;
        if(L<=mid) ans=max(ans,pre(u<<1,x,L,R,l,mid));
        if(R>mid) ans=max(ans,pre(u<<1|1,x,L,R,mid+1,r));
        return ans;
    }
    inline int nxt(rint u,rint x,rint L,rint R,rint l,rint r)
    {
        if(L<=l&&r<=R)
        {
            return trr[u].nxt(x);
        }
        rint mid=l+r>>1,ans=2147483647;
        if(L<=mid) ans=min(ans,nxt(u<<1,x,L,R,l,mid));
        if(R>mid) ans=min(ans,nxt(u<<1|1,x,L,R,mid+1,r));
        return ans;
    }
}trrr;
signed main() 
{  
    n=_;rint q=_;
    for(rint i=1;i<=n;++i) a[i]=_;
    trrr.build(1,1,n);
    while(q--)
    {
        rint op=_;
        if(op==1)
        {
            rint l=_,r=_,k=_;
            out(trrr.query1(1,l,r,1,n,k)+1);pc('\n');
        }
        else if(op==2)
        {
            rint l=_,r=_,k=_;
            out(trrr.query2(1,l,r,k));pc('\n');
        }
        else if(op==3)
        {
            rint k=_,x=_;
            trrr.modify(1,k,x,1,n);
            a[k]=x;
        }
        else if(op==4)
        {
            rint l=_,r=_,k=_;
            out(trrr.pre(1,k,l,r,1,n));pc('\n');
        }
        else
        {
            rint l=_,r=_,k=_;
            out(trrr.nxt(1,k,l,r,1,n));pc('\n');
        }
    }
    return 0;   
} 
//我也要写吗

:::

P1552 [APIO2012] 派遣

熟悉吗，还是这个题。

不难想到一个经典的技巧，对于节点 u 其子树内的 dfn 序是连续的，即 [dfn_u,dfn_u+siz_u-1] 然后，我们就可以考虑树套树来计算答案了。

不过时间复杂度 \mathcal{O}(n \log^3 n)，而且题目所给的时间限制为 0.5 秒，我们是很难卡过的，只是作为一种思路。（话说 \mathcal{O}(n \log^3 n) 跑不过 \mathcal{O}(n^2\log n) 是什么鬼）

可持久化 \texttt{FHQ-Treap}

因为带旋 \texttt{Treap} 的旋转操作会改变多个节点的父子关系，难以追踪历史版本，所以不适合直接可持久化。而 \texttt{FHQ-Treap} 的所有操作只改变从根到叶子路径上的节点，天然支持可持久化。

那么我们如何可持久化呢？根据可持久化的思想，即我们只要修改了树的形态就可以克隆一个节点然后连接即可。

我们对于每个不同的版本可以有一个不同的根，从这个根来查询答案就是这个版本的答案，而且我们只克隆需要修改的节点其他的不变，这样可以保证空间不炸。

由于每次操作只新建 \mathcal{O}(\log n) 个节点，总空间复杂度为 \mathcal{O}((N+M)\log N)，因此开 N \times 50 的数组通常是安全的。

P3835 【模板】可持久化平衡树

不妨看看代码理解。

:::success[Ac Code]

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
// #define int long long 
#define ull unsigned long long
// #define R register
#define rint register int
#define _ read<int>()
inline bool blank(const char &x)
{
    return !(x^13)||!(x^32)||!(x^10)||!(x^9);
}
template<class T>inline T read()
{
    T r=0,f=1;char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
inline void read(string &x) 
{
    x="";char a=gc(); 
    for(;blank(a)&&(a^-1);a=gc()); 
    for(;!blank(a)&&(a^-1);a=gc()) x+=a;
}
mt19937 rnd(time(0));
const int N=5e5+10;
struct FHQ_Treap
{
    int cnt,root[N];
    struct Node
    {
        int l,r,siz,pri,x;
    }tr[N*50];
    inline int neo(rint x)
    { 
        tr[++cnt]={0,0,1,(int)rnd(),x};
        return cnt;
    }
    inline int clone(rint u)
    {
        if(!u) return 0;
        tr[++cnt]=tr[u];
        return cnt;
    }
    inline void pushup(rint u)
    {
        tr[u].siz=tr[tr[u].l].siz+1+tr[tr[u].r].siz;
    }
    inline pair<int,int> split(rint u,rint k)
    {
        if(!u) return {0,0};
        u=clone(u);
        if(tr[u].x<=k)
        {
            auto x=split(tr[u].r,k);
            tr[u].r=x.first;
            pushup(u);
            return {u,x.second};
        }
        else
        {
            auto x=split(tr[u].l,k);
            tr[u].l=x.second;
            pushup(u);
            return {x.first,u};
        }
    }
    inline int merge(rint u,rint v)
    {
        if(!u||!v) return u|v;
        if(tr[u].pri<tr[v].pri)
        {
            u=clone(u);
            tr[u].r=merge(tr[u].r,v);
            pushup(u);
            return u;
        } 
        else
        {
            v=clone(v);
            tr[v].l=merge(u,tr[v].l);
            pushup(v);
            return v;
        }
    }
    inline void ins(rint v,rint u,rint x)
    {
        auto [l,r]=split(root[v],x);
        root[u]=merge(merge(l,neo(x)),r);
    }
    inline void erase(rint v,rint u,rint x)
    {
        auto [l,midr]=split(root[v],x-1);
        auto [mid,r]=split(midr,x);
        if(mid) mid=clone(mid),mid=merge(tr[mid].l,tr[mid].r);
        root[u]=merge(merge(l,mid),r);
    }
    inline int kkth(rint v,rint x)
    {
        auto [l,r]=split(root[v],x-1);
        rint ans=tr[l].siz+1;
        return ans;
    }    
    inline int kth(rint v,rint k)
    {
        rint u=root[v];
        while(u)
        {
            if(tr[tr[u].l].siz+1==k) return tr[u].x;
            if(tr[tr[u].l].siz>=k) u=tr[u].l;
            else
            {
                k-=(tr[tr[u].l].siz+1);
                u=tr[u].r;
            }
        }
        return -1;
    }
    inline int pre(rint v,rint x) 
    {
        auto [l,r]=split(root[v],x-1);
        if (!l) return -2147483647;
        rint u=l;
        while(tr[u].r) u=tr[u].r;
        return tr[u].x;
    }
    inline int nxt(rint v,rint x) 
    {
        auto [l,r]=split(root[v],x);
        if(!r) return 2147483647;
        rint u=r;
        while(tr[u].l) u=tr[u].l;
        return tr[u].x;
    }
}tr;

signed main() 
{  
    rint q=_;
    for(rint i=1;i<=q;++i)
    {
        rint v=_,op=_,x=_;

        if(op==1) tr.ins(v,i,x);
        else if(op==2) tr.erase(v,i,x);
        else
        {
            if(op==3) out(tr.kkth(v,x)),pc('\n');
            else if(op==4) out(tr.kth(v,x)),pc('\n');
            else if(op==5) out(tr.pre(v,x)),pc('\n');
            else out(tr.nxt(v,x)),pc('\n');
            tr.root[i]=tr.root[v];
        }
    }
    return 0;   
} 
//穗穗平安～

:::

带旋 \texttt{Treap}

首先，带旋 \texttt{Treap} 最大的特点就是左旋右旋。

左旋

如上图，现在我们把 B 左旋，这个时候 D 就成为根结点，然后 B 要成为 D 的左子树，但是和 E 冲突，因为是 BST 所以 B 肯定小于 E 所以把 E 接到 B 的右子树。

来看看改变了什么，首先根（B）的右子树（D）变为其右子树（D）的左子树（E），其次根（B）的右子树（D）的左子树变为根（B）。

:::success[Code]

inline int zag(rint u)
{
    rint v=tr[u].r;
    tr[u].r=tr[v].l;
    tr[v].l=u;
    pushup(u);
    pushup(v);
    return v;
}

:::

右旋

如上图，我们先不管具体的值，只看大小关系，我们需要将它从 F 那里右旋，将 F 往下调，于是 B 变为根节点，但是你发现 F>B 所以 F 变为 B 的右节点，可是 B 已经有个右节点 E 了，怎么办呢？注意到已 B 为根的子树全都小于 F 所以 E 应该在 F 的左子树。

如上图，现在右旋完了，我们对比一下看一下改变了啥，首先就是 B 的右子树变为以 F 为根的子树，F 的左子树从 B 变为 B 的右子树。

:::success[Code]

inline int zig(rint u)
{
    rint v=tr[u].l;
    tr[u].l=tr[v].r;
    tr[v].r=u;
    pushup(u);
    pushup(v);
    return v;
}

:::

插入

首先，我们要保证 BST 性质不被破坏，那么我们就按照 BST 性质，找到一个空节点建立这个新插入的点，然后如果破坏了小根堆性质，那么就左旋或者右旋调整过来。

:::success[Code]

inline int insert(rint u,rint x)//当前的点为u，插入值为x的点
{
    if(!u) return neo(x);
    if(x==tr[u].x) tr[u].cnt++;//相等
    else if(x<tr[u].x)
    {
        tr[u].l=insert(tr[u].l,x);
        if(tr[tr[u].l].s>tr[u].s) u=zig(u);//左儿子优先级高，右旋
    }
    else
    {
        tr[u].r=insert(tr[u].r,x);
        if(tr[u].s>tr[tr[u].r].s) u=zag(u);//右儿子优先级高，左旋
    }
    pushup(u);
    return u;
}

:::

删除

这个很有意思，首先我们先根据 BST 的性质，找到这节点，我们分类讨论一下：

• 如果这个节点不止一个：
  • 删掉就好。
• 如果只有一个：
  • 如果是叶子节点：
  • 删掉就好。
  • 如果是有一个左节点：
  • 将要删掉的节点左旋，然后就变成叶子节点，删掉就好。
  • 如果是有一个右节点：
  • 将要删掉的节点右旋，然后就变成叶子节点，删掉就好。
  • 如果两个节点都有：
  • 比较两个节点的优先级，优先级低的左旋或者右旋上去，然后要删掉的节点变成叶子节点，删掉就好。

:::success[Code]

inline int erase(rint u,rint x)
{
    if(!u) return 0;//没这个节点
    if(x<tr[u].x)//在左子树
    {
        tr[u].l=erase(tr[u].l,x);
    }
    else if(x>tr[u].x)//在右子树
    {
        tr[u].r=erase(tr[u].r,x);
    }
    else//就是这个节点
    {
        if(tr[u].cnt>1) tr[u].cnt--;//大于一个
        else
        {
            if(!tr[u].l&&!tr[u].r) return 0;//删掉
            else if(tr[u].l&&!tr[u].r)
            {
                u=zig(u);tr[u].r=erase(tr[u].r,x);//删除，注意到这里不是叶子节点还要继续右旋到叶子节点
            }
            else if(!tr[u].l&&tr[u].r)
            {
                u=zag(u);tr[u].l=erase(tr[u].l,x);//同理
            }
            else 
            {
                if(tr[tr[u].l].s<tr[tr[u].r].s)//左边的小，右旋
                {
                    u=zig(u);tr[u].r=erase(tr[u].r,x);
                }
                else
                {
                    u=zag(u);tr[u].l=erase(tr[u].l,x);
                }                
            }
        }
    }
    pushup(u);
    return u;
}

:::

查询排名

怎么查询 x 的排名呢？还是按照 BST 的性质找 x。

• 找到了：
  • 返回之前和加上左子树的大小加上 1。
• 如果在左子树：
  • 继续找。
• 如果在右子树：
  • 加上左子树和这个节点本身的大小继续找。

:::success[Code]

inline int find1(rint u,rint x)
{
    if(!u) return 1;//没有x这个节点，排名1
    if(x==tr[u].x)
    {
        return tr[tr[u].l].siz+1;//左子树大小加1
    }
    else if(x<tr[u].x)
    {
        return find1(tr[u].l,x);
    }
    else
    {
        return tr[tr[u].l].siz+tr[u].cnt+find1(tr[u].r,x);
    }
}

:::

查询第 k 小

怎么查询第 k 小的数呢？和 \texttt{FHQ-Treap} 有点像，不过我们这次用递归来找。

:::success[Code]

inline int find2(rint u,rint k)
{
    if(!u) return -114514;//没有这个排名
    if(k<=tr[tr[u].l].siz)//在左子树中
    {
        return find2(tr[u].l,k);
    }
    else if(k<=tr[tr[u].l].siz+tr[u].cnt)//就是这个节点
    {
        return tr[u].x;
    }
    else//在右子树
    {
        return find2(tr[u].r,k-tr[tr[u].l].siz-tr[u].cnt);
    }
}

:::

查询前驱

怎么查询 x 的前驱？我们来分情况讨论一下：

• 如果当前节点的值大于等于 x：
  • 说明 x 的前驱在左子树。
• 否则，查询先查询右子树有没有比 x 小点的，最后和当前节点取 \max。

:::success[Code]

inline int pre(rint u,rint x)//查询 x 前驱
{
    if(!u) return -1145141919810;//这个子树中没有 x 前驱
    if(x<=tr[u].x) return pre(tr[u].l,x);//前驱不是右子树和当前节点
    return max(tr[u].x,pre(tr[u].r,x));
}

:::

查询后继

怎么查询 x 的后继呢？来讨论一下：

• 如果当前节点小于等于 x：
  • 后继肯定不在左子树或者当前节点，去右子树看看。
• 如果当前节点大于 x：
  • 去左子树看看大于 x 的，和当前节点取 \min。

:::success[Code]

inline int nxt(rint u,rint x)//查询x后继
{
    if(!u) return 1145141919810;//这个子树没有 x 后继
    if(tr[u].x<=x) return nxt(tr[u].r,x);
    return min(tr[u].x,nxt(tr[u].l,x)); 
}

:::

完整代码

:::success[Ac Code]

#include <bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define R register
#define int long long
#define rint register int
#define _ read<int>()
inline bool blank(R const char &x){return !(x^32)||!(x^10)||!(x^13)||!(x^9);}
template<class T>inline T read()
{
    R T r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(R char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
const int N=1e5+10;
mt19937 rnd(time(0)*114514/1919810);
int root=0;
struct Treap
{
    struct Tree{int l,r,siz,cnt,x,s;}tr[N];
    int cnt;
    inline int neo(rint x)
    {
        tr[++cnt]={0,0,1,1,x,(int)rnd()};
        return cnt;
    }
    inline void pushup(rint u){tr[u].siz=tr[tr[u].l].siz+tr[tr[u].r].siz+tr[u].cnt;}
    inline int zag(rint u)//左旋
    {
        rint v=tr[u].r;
        tr[u].r=tr[v].l;
        tr[v].l=u;
        pushup(u);pushup(v);
        return v;
    }
    inline int zig(rint u)//右旋
    {
        rint v=tr[u].l;
        tr[u].l=tr[v].r;
        tr[v].r=u;
        pushup(u);pushup(v);
        return v;
    }
    inline int insert(rint u,rint x)//当前的点为u，插入值为x的点
    {
        if(!u) return neo(x);
        if(x==tr[u].x) tr[u].cnt++;//相等
        else if(x<tr[u].x)
        {
            tr[u].l=insert(tr[u].l,x);
            if(tr[tr[u].l].s>tr[u].s) u=zig(u);//左儿子优先级高
        }
        else
        {
            tr[u].r=insert(tr[u].r,x);
            if(tr[u].s>tr[tr[u].r].s) u=zag(u);//右儿子优先级第
        }
        pushup(u);
        return u;
    }
    inline int erase(rint u,rint x)
    {
        if(!u) return 0;//没这个节点
        if(x<tr[u].x)//在左子树
        {
            tr[u].l=erase(tr[u].l,x);
        }
        else if(x>tr[u].x)//在右子树
        {
            tr[u].r=erase(tr[u].r,x);
        }
        else//就是这个节点
        {
            if(tr[u].cnt>1) tr[u].cnt--;//大于一个
            else
            {
                if(!tr[u].l&&!tr[u].r) return 0;//删掉
                else if(tr[u].l&&!tr[u].r)
                {
                    u=zig(u);tr[u].r=erase(tr[u].r,x);//删除，注意到这里不是叶子节点还要继续右旋旋到叶子节点
                }
                else if(!tr[u].l&&tr[u].r)
                {
                    u=zag(u);tr[u].l=erase(tr[u].l,x);//同理
                }
                else 
                {
                    if(tr[tr[u].l].s<tr[tr[u].r].s)//左边的小，右旋
                    {
                        u=zig(u);tr[u].r=erase(tr[u].r,x);
                    }
                    else
                    {
                        u=zag(u);tr[u].l=erase(tr[u].l,x);
                    }                
                }
            }
        }
        pushup(u);
        return u;   
    }
    inline int find1(rint u,rint x)
    {
        if(!u) return 1;//没有x这个节点，排名1
        if(x==tr[u].x)
        {
            return tr[tr[u].l].siz+1;//左子树大小加1
        }
        else if(x<tr[u].x)
        {
            return find1(tr[u].l,x);
        }
        else
        {
            return tr[tr[u].l].siz+tr[u].cnt+find1(tr[u].r,x);
        }
    }
    inline int find2(rint u,rint k)
    {
        if(!u) return -114514;//没有这个排名
        if(k<=tr[tr[u].l].siz)//在左子树中
        {
            return find2(tr[u].l,k);
        }
        else if(k<=tr[tr[u].l].siz+tr[u].cnt)//就是这个节点
        {
            return tr[u].x;
        }
        else//在右子树
        {
            return find2(tr[u].r,k-tr[tr[u].l].siz-tr[u].cnt);
        }
    }
    inline int pre(rint u,rint x)//查询 x 前驱
    {
        if(!u) return -1145141919810;//这个子树中没有 x 前驱
        if(tr[u].x>=x) return pre(tr[u].l,x);//前驱不是右子树和当前节点
        return max(tr[u].x,pre(tr[u].r,x));
    }
    inline int nxt(rint u,rint x)//查询x后继
    {
        if(!u) return 1145141919810;//这个子树没有 x 后继
        if(tr[u].x<=x) return nxt(tr[u].r,x);
        return min(tr[u].x,nxt(tr[u].l,x)); 
    }
}tr;

signed main()
{  
    rint q=_;
    while(q--)
    {
        rint op=_,x=_;
        if(op==1)
        {
            root=tr.insert(root,x);
        }
        else if(op==2)
        {
            root=tr.erase(root,x);
        }
        else if(op==3)
        {
            out(tr.find1(root,x));pc('\n');
        }
        else if(op==4)
        {
            out(tr.find2(root,x));pc('\n');
        }
        else if(op==5)
        {
            out(tr.pre(root,x));pc('\n');
        }
        else 
        {
            out(tr.nxt(root,x));pc('\n');
        }
    }
    return 0;
}

:::

总结

个人认为这两种 \texttt{Treap} 各有各的优点，\texttt{FHQ-Treap} 简单易上手，可持久化、区间操作比较简单，带旋 \texttt{Treap} 左旋右旋个人感觉比较难理解，不过它常数比 \texttt{FHQ-Treap} 小（也许是我写法的问题），实际解决问题中，还是按需选择吧。

upd

2026/2/8：感谢 @JasmineCloud__ 指出的错误，已修正。

2026/3/28： 增加了文艺平衡树部分，并修改了一些错误。

2026/5/23：添加了启发式合并板块。

2026/5/30：添加了树套树板块与可持久化 \texttt{FHQ-Treap} 部分，并修改了 split 部分，并优化许多笔误。

2026/6/6：添加了动态分裂部分（？应该是叫这个名字）还增加了些例题。

欢迎各位指出我的错误！