浅谈线段树合并与分裂

· · 算法·理论

是 Junly 用来讲评的文章，索性发出去吧（x）

线段树是通过将区间多次一分为二（操作深度为 \log n），将结合律信息处理到子问题的数据结构。

之前所提及的信息维护方式主要以多棵独立的线段树上的区间操作为主。现在要实现的主要是跨线段树的操作，即将多棵线段树的信息归并到一棵线段树上、和将一棵线段树的信息分裂到多棵线段树上。

这分为线段树合并与线段树分裂两个部分。只提供板子题的代码。

:::align{center}

线段树合并

:::

内核

我们知道线段树能够维护的信息是具有结合律的，这意味着我们不仅可以合并子树信息，还可以合并两棵线段树。

比如说，维护两个求和的区修区查线段树。那么新树可以这么求：先把所有叶节点信息合并（就是新叶子等于旧的两个叶子之和），再多次在新树上 pushup 即可。

其操作本质上就是建出一棵新的线段树，而这棵线段树的每个节点都是两棵原线段树对应节点合并后的结果。这里直接合并叶子，再多次 pushup，是最方便也是最典型的合并方法。

应用场景

显然每次不可能都建造一棵新的线段树吧。

所以，线段树合并通常应用于动态开点线段树上，且多为权值线段树。对于两棵结构相同（维护同一值域区间）的动态开点线段树，合并操作将它们的对应节点信息聚合为一棵新树，直接将信息并入其中一棵树中。常见场景包括：树上差分统计子树信息、整体二分中合并不同状态的集合、可持久化线段树中复用历史版本等。

除了合并点之外，若需要保留原树不被破坏，在合并时遇到一方为空或需要修改节点时，应新建节点并复制信息。故，空间复杂度与操作次数相关，通常为 \mathcal{O}(m \log n)。合并时两棵树可能存在节点不共存的情况，此时通过直接指向存在的节点来节省时间和空间。

实现

将线段树 b 合并至 a 的步骤如下：

inline int merge(int a,int b,int l,int r) { // 最后 a 即为合并后的新线段树 
    if(!a) return b;
    if(!b) return a;
    if(l==r) {
        merge_node(a,b);
        return a;
    }
    int mid=(l+r)>>1;
    L[a]=merge(L[a],L[b],l,mid);
    R[a]=merge(R[a],R[b],mid+1,r);
    pushup(a);
    return a;
}

:::warning[关于复杂度]{open} 1. 对于叶子规模为 n 的满线段树 A，将其与其它线段树进行一次线段树合并的最坏复杂度是多少？

A. \mathcal{O}(1)\ B. \mathcal{O}(\log n)\ C. \mathcal{O}(n)\ D. \mathcal{O}(n \log n)\ E. \mathcal{O}(n \log^2 n)

2. 对于叶子规模为 n 的满线段树 A，将其与其它线段树进行一次线段树合并的最好复杂度是多少？

A. \mathcal{O}(1)\ B. \mathcal{O}(\log n)\ C. \mathcal{O}(n)\ D. \mathcal{O}(n \log n)\ E. \mathcal{O}(n \log^2 n)

3. 通常情况下，对权值线段树进行多次合并，平均下来每次合并的复杂度是多少？

A. \mathcal{O}(1)\ B. \mathcal{O}(\log n)\ C. \mathcal{O}(n)\ D. \mathcal{O}(n \log n)\ E. \mathcal{O}(n \log^2 n) :::

:::info[解答] 对于两颗满线段树，合并操作的复杂度是 \mathcal{O}(n)+\mathcal{O}(\frac{n}{2})+\mathcal{O}(\frac{n}{4})+\mathcal{O}(\frac{n}{8})+\dots+\mathcal{O}(\frac{n}{2^k})=\mathcal{O}(n) 的。

对于一棵满线段树和另外一棵空线段树，直接在根上头就返回了，其复杂度就是 \Omega(1)。

对于权值线段树，总点数和 n 的规模相差并不大。并且合并时一般不会重复地合并某个线段树，所以最终增加的点数大致是 n \log n 级别的。

这样，总的复杂度就是 \mathcal{O}(n \log n) 级别的。那平均下来，每次复杂度就是 \mathcal{O}(\log n)。 :::

例题 1

给定一棵树，树上的每个节点都有一个序列。你需要进行 m 次操作，每次操作给定三个正整数 x,y,z(x,y \in [1,n])，你需要在树链 x \leftrightarrow y 上的每个点的序列中都插入一个数 z。

问若干次操作后，每个点所代表序列的众数是什么。如果存在多个众数，输出较小的那个。如果序列中没有数字，输出 0。

:::success[观察] 题目本身挺清新。它是离线的，不需要在线查询。这种情况下差分太好使了。

考虑树上差分。定义 \textrm{lca}(a,b) 表示点 a,b 的最近公共祖先，\textrm{fa}(a) 代表 a 的直接父节点。则每个操作等价于：

这样一来，通过后序遍历累加子树信息，即可还原每个节点的实际计数。

问题是，这要使用怎样的数据结构来维护？ :::

:::success[注意] 我们需要维护的数据结构需要具备下面的功能：

如果使用哈希表或者朴素的桶来统计，明显 \mathcal{O}(n \times m) 是无法承受的。\ 而虽然本题涉及“众数”，分块思想仍然无法解决。树上分块需首先将任意的路径 x \to y 分解成 \sqrt{\textrm{len}} 个块，再对块中的元素进行统计。如果再对 z 的值域分块，明显时间复杂度为 \mathcal{O}(\sqrt{\textrm{len}} \times \sqrt{z} \times m)\approx\mathcal{O}(10^{10})，完全无法解决此题。

那要使用具体哪个数据结构，做什么操作？ :::

:::success[启示] 对树上的每个点开一棵值域线段树啊。

每次操作都在具体的位置 modify，等待所有操作都做完了之后，自下往上合并不就好了。 :::

:::error[常见错误]{close} 如果要使用 lca，则 dep 数组必须明确定义。

该代码中不能在 dfs 函数中将 dep 更新搬到内层的 for 循环。否则，dep_0=dep_1=1，界限不明确，可能就会让 lca=0。这就只有 80 分。 :::

:::success[代码]

#include<bits/stdc++.h>
#define N 100002
using namespace std;
int rt[N],sum[N<<7],id[N<<7],lc[N<<7],rc[N<<7],idx;
int n,m,fr,to,wi,f[N][22],dep[N],ans[N];
vector<int> vec[N];
inline void pushup(int p){
    if(sum[lc[p]]>=sum[rc[p]]){
        sum[p]=sum[lc[p]];
        id[p]=id[lc[p]];
    }else{
        sum[p]=sum[rc[p]];
        id[p]=id[rc[p]];
    }
}
inline void change(int &p,int l,int r,int plc,int del){ // 单修
    if(!p) p=++idx;
    if(l==r){
        sum[p]+=del;
        id[p]=l;
        return;
    }
    int mid=l+r>>1;
    if(plc<=mid) change(lc[p],l,mid,plc,del);
    else change(rc[p],mid+1,r,plc,del);
    pushup(p);
    return;
}
inline int merge(int x,int y,int l,int r){
    if(!x) return y;
    if(!y) return x;
    if(l==r){
        sum[x]+=sum[y];
        return x;
    }
    int mid=l+r>>1;
    lc[x]=merge(lc[x],lc[y],l,mid);
    rc[x]=merge(rc[x],rc[y],mid+1,r);
    pushup(x);
    return x;
}
inline int Lca(int x,int y){ // 表示两个点的最近公共祖先
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19; i>=0; i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=19; i>=0; i--) if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
    return f[x][0];
}
inline void dfs(int x,int fa){ // 预处理所有点的最近公共祖先（LCA）
    f[x][0]=fa; // f[x][i] 表示 x 往上跳 2^i 格能够跳到哪里
    dep[x]=dep[fa]+1;
    for(int i=1; i<20; i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=0; i<vec[x].size(); i++){
        int y=vec[x][i];
        if(y==fa) continue;
        dfs(y,x);
    }
}
inline void big_merge(int x){
    for(int i=0; i<vec[x].size(); i++){
        int y=vec[x][i];
        if(y==f[x][0]) continue;
        big_merge(y);
        merge(rt[x],rt[y],1,N-2);
    }
    ans[x]=id[rt[x]];
    if(sum[rt[x]]==0) ans[x]=0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++) rt[i]=++idx;
    for(int i=1; i<n; i++){
        cin>>fr>>to;
        vec[fr].push_back(to);
        vec[to].push_back(fr);
    }
    dfs(1,0);
    while(m--){
        cin>>fr>>to>>wi;
        int D=Lca(fr,to);
        change(rt[fr],1,N-2,wi,1);
        change(rt[to],1,N-2,wi,1);
        change(rt[D],1,N-2,wi,-1);
        if(D!=1) change(rt[f[D][0]],1,N-2,wi,-1);
    }
    big_merge(1);
    for(int i=1; i<=n; i++) cout<<ans[i]<<"\n";
    return 0;
}

:::

例题 2

给定一棵树，对于每个节点 u 静态地求出：

\sum_{i \in \textrm{subtree}(u)} [p_i > p_u]

中括号是艾弗森括号，若其内部逻辑命题为真则值为 1，否则为 0。

:::success[观察] 题目中每个节点本身的权值是不同的，所以不能够直接把儿子的值相加。

我们要统计整个子树的信息，但是直接下去 \mathcal{O}(n^2) 肯定要爆掉。

从树本身考虑。有没有什么方法不用访问子树内部所有的信息，就能够统计比其大的数？ :::

:::success[注意] 从树的位置关系看，不足以快速统计。

考虑到只用管大小的相对关系，所以可以先将值域离散化。

那离散化之后，值域大小就变成 1 \sim n 了，可以当成数组下标了。 :::

:::success[启示] 那不就对每个结点开个值域线段树，每个父亲信息来自其儿子信息。

合并子节点的信息之后，对每个节点区查 (\textrm{rank}(p_i),n]，单修 T_{\textrm{rank}(p_i)} \gets T_{\textrm{rank}(p_i)}+1。

做完了嘛。 :::

例题 3

给定一棵有根的二叉树，其叶子节点的点权给定（为 w_i），其余点点权有 p_i 的概率为其子节点权值最大，有 1-p_i 概率为其子节点权值最小。

定义 1 号节点的权值一共有 m 种可能，其中权值第 i 小的可能性的权值为 V_i，概率为 D_i。求：

(\sum_{i=1}^{m} i \times V_i \times D_i^2) \bmod 998244353

:::success[观察] 有一个性质：因为 p \neq 0 且 p \neq 1，所以每个叶子节点的权值都一定会对其祖先造成贡献。

这个不难理解啊：二叉树中每个节点只有最多 2 个儿子，那每个节点的权值就可以当最大值或者当最小值。因此，可以构造出一种取最大最小方案，让该节点的权值等于其子树的叶子中对应的权值。

那好了，我们可以直接对权值进行离散化，求出来对于根节点来说每个节点的 \textrm{rank}，那 i \times V_i 好办了。

下视 n 和值域同阶。

思考：随后应当如何统计信息？ :::

:::success[注意] 注意到要求出每个结点的信息就可以考虑从其直接儿子中更新。考虑树形 dp。

我们直接设 f_{i,j} 表示位置 i 离散化之后的权值为 j 的概率。有初始化：对于叶子节点 \ell，f_{\ell,\textrm{rank}(\ell)}=1，其余皆为 0。

对于非叶子节点，这个数组好统计、并且好转移吗？确实。

对于单子非叶节点，直接继承其 f 数组即可。

对于双子非叶节点 u，定义其左儿子节点为 l，右儿子节点为 r，取到最小值概率 q_u=1-p_u，考虑下述两种情况。

全部加起来，结果算出来：

f_{u,i}=f_{L,i} \times (p_u \times \sum_{j<i} f_{R,j} + q_u \times \sum_{j>i} f_{R,j})+f_{R,i} \times (p_u \times \sum_{j<i} f_{L,j} + q_u \times \sum_{j>i} f_{L,j})

诶坏了，这个式子朴素转移下来貌似要 \mathcal{O}(n^2) 的时间复杂度，爆了爆了。

此时又应该怎么办呢？ :::

:::success[启示] 首先排除前缀和优化。那为什么前缀和优化会失败？

朴素的前缀和优化思路是：对每个节点 u，先花 \mathcal{O}(n) 时间算出其儿子的概率分布前缀和，再花 \mathcal{O}(n) 时间逐点计算出 f_u。这样一来，单次转移是 \mathcal{O}(n) 的，那总复杂度自然就是 \mathcal{O}(n^2)。

瓶颈是我们在每个节点都“平等地”处理了整个值域，而实际上，许多值域区间内概率是零，这些无效计算被大量浪费了。

解决问题的关键，是用动态开点线段树来替代完整的数组，只存储“有概率”的位置。线段树中的一个节点 T_u，对应值域区间 [l, r]，其 sum 值存储 \sum\limits_{j=l}^{r} f_{u,j}，即该区间内的概率总和。

当我们合并左儿子 L 和右儿子 R 的线段树时，核心思想是：将另一个儿子整个区间的概率总和，作为“大小关系”的贡献，一次性乘到当前区间上，而不是深入到每个单点。

具体地，设我们正在递归合并树 u（来自 L）和树 v（来自 R），当前值域区间为 [l, r]。我们额外维护两个累积系数：

合并过程遵循以下分治逻辑。

最终，在根节点的线段树上做一次遍历，对每个叶子 i 取出其概率 D_i = f_1(i)，代入公式 \sum_{i=1}^m i \cdot V_i \cdot D_i^2 计算即可得到答案。

此题可解。 :::

:::align{center}

线段树分裂

:::

内核

线段树分裂可以看作合并的逆操作：将一棵动态开点线段树 T 按照某个阈值拆成两棵树 T_1 和 T_2，使得 T_1 中包含 T 里值域区间上前 k 个元素（或值 \le x 的部分），T_2 中包含剩余元素。由于线段树的节点天然按值域二分，我们可以递归地“掰开”节点，一边保留原结构，一边分离出新的节点，最终仍保证两棵树结构的正确性。

分裂的核心是对每个节点，根据分裂阈值判断它的左右儿子是完全属于一边，还是需要被切开。如果一个节点对应的值域区间完全在某一侧，则直接将其整棵子树分配给对应树；若跨过分界点，则需要递归处理儿子，必要时复制节点，从而保证原信息和分裂后信息的完整性。

应用场景

线段树分裂通常与线段树合并配合使用，用于处理值域上的序关系以及多重集的拆分与合并。

与合并类似，为了高效利用节点，线段树分裂通常应用于动态开点线段树。分裂过程会产生新节点，总节点数仍与操作次数及值域对数规模相关，空间复杂度约为 \mathcal{O}((n+m)\log n)。

实现

分裂可以按元素个数（排名）分裂：给定线段树 a（根为 root），要求将其分裂为两棵树 x 和 y，使得 x 包含原树中排名在 [1,k] 的所有元素，y 包含排名在 k+1\sim \text{total} 的元素，且新树仍为合法线段树。

如果要按具体值 v 分裂，改一改判断条件即可，逻辑完全对偶。

下面给一份按下标区间分裂的代码。

inline void split(int &x,int &y,int l,int r,int pl,int pr){
    if(!x or !sum[x]) return;
    if(pl<=l and pr>=r){
        y=x,x=0;
        return;
    }
    y=++idx;
    int mid=l+r>>1;
    if(pl<=mid) split(lc[x],lc[y],l,mid,pl,pr);
    if(pr>mid) split(rc[x],rc[y],mid+1,r,pl,pr);
    pushup(x); pushup(y); 
}

:::warning[关于复杂度]{open} 1. 将一棵包含 n 个不同元素的线段树，按排名 k 分裂成两棵树，最坏时间复杂度是？

A. \mathcal{O}(\log k)\ B. \mathcal{O}(\log n)\ C. \mathcal{O}(n)\ D. \mathcal{O}(k \log n)\ E. \mathcal{O}(n \log n)

2. 在一次分裂中，新建的节点数量与什么直接相关？（可多选）

A. 树的总节点数。\ B. 分裂阈值 [l,r]。\ C. 值域的大小 n。 :::

:::info[解答] 按排名分裂时，每一层至多递归一个方向，若该层节点跨过阈值，则可能新建一个对应节点。整个过程只沿着从根到叶的路径走，因此复杂度为 \mathcal{O}(\log n)。

分裂时新建的节点正是那些原本属于同一节点、但因为阈值切割而需要拆分成两部分的“交界”节点。从根到叶的路径上，每发生一次“切开”就会产生一个新节点。 :::

例题 4

维护一个多重集，支持以下操作（在线）：

  • 0 p x y：将可重集 p 中值在 [x,y] 范围内的所有数分裂到一个新的可重集中（p 中原有这些数被移除）。
  • 1 p t：将可重集 t 合并入可重集 p 中，此后 t 变为空集。
  • 2 p x q：向可重集 p 中加入 x 个值为 q 的数。
  • 3 p x y：查询可重集 p 中值在 [x,y] 内的数的个数。
  • 4 p k：查询可重集 p 中第 k 小的数，不存在则输出 -1。

编号 p,t 均为已存在的集合编号，操作过程中集合数量会动态增加。值域 1 \le q \le n，操作总数 m \le 2\times 10^5，n \le 2\times 10^5。

:::success[观察] 题目要求同时支持合并、加点、区间计数和求第 k 小。

这些都能被线段树直接完成。

如果要按值域区间分裂，又该如何完成？ :::

:::success[注意] 每个可重集可以用一棵权值线段树维护：叶节点存储该值的出现次数，内部节点维护区间内元素个数。那么：

:::success[启示] 核心操作就是两次分裂 + 一次合并（如果需要的话）。细节上，分裂实现可以仿照前面的按值分裂写法，判断当前区间中点与分裂值的关系。若当前区间完全在分裂点左侧，则全部分给 x；完全在右侧，全部分给 y；否则递归。

此题虽然操作类型多，但每种操作都可以用 \mathcal{O}(\log n) 的线段树操作解决，总复杂度 \mathcal{O}(m \log n)。此题是线段树分裂的模板题，熟练掌握后，可以将其应用于更多需要动态分拆值域集合的问题中。 :::

:::success[代码]

#include<bits/stdc++.h>
//#define getchar getchar_unlocked
using namespace std;
using ll=long long;
inline int read(){
    int s=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s;
}
const int N=2e5+5;
int n,m,root[N],lc[N<<6],rc[N<<6],opt,q,x,y,tot=1,idx;
ll sum[N<<6];
inline void pushup(int p){sum[p]=sum[lc[p]]+sum[rc[p]];}
inline void change(int &p,int l,int r,int x,int y){ // 单点修改 
    if(!p) p=++idx;
    sum[p]+=y;
    if(l==r) return;
    int mid=l+r>>1;
    if(x<=mid) change(lc[p],l,mid,x,y);
    else change(rc[p],mid+1,r,x,y);
    pushup(p);
}
inline void split(int &x,int &y,int l,int r,int pl,int pr){
    if(!x or !sum[x]) return;
    if(pl<=l and pr>=r){
        y=x; x=0;
        return;
    }
    y=++idx;
    int mid=l+r>>1;
    if(pl<=mid) split(lc[x],lc[y],l,mid,pl,pr);
    if(pr>mid) split(rc[x],rc[y],mid+1,r,pl,pr);
    pushup(x); pushup(y); 
}
inline int merge(int A,int B){ // 祖传破坏合并 
    if(!A or !B) return A+B; // 一方非空即使用另一方代替 
    sum[A]+=sum[B];
    lc[A]=merge(lc[A],lc[B]);
    rc[A]=merge(rc[A],rc[B]);   
    return A;
}
inline ll ask(int p,int l,int r,int s,int t){ // 区间查询 
    if(!p) return 0;
    if(l>=s and r<=t) return sum[p];
    int mid=l+r>>1; ll ans=0;
    if(s<=mid) ans+=ask(lc[p],l,mid,s,t);
    if(t>mid) ans+=ask(rc[p],mid+1,r,s,t);
    return ans;
}
inline int kth(int p,int l,int r,int k){ // 找到序列中第 k 小的值 
    if(l==r) return l;
    int mid=l+r>>1; ll s=sum[lc[p]];
    if(s>=k) return kth(lc[p],l,mid,k);
    else return kth(rc[p],mid+1,r,k-s);
} 
int main(){
    n=read(); m=read();
    for(int i=1; i<=n; i++) change(root[1],1,n,i,read());
    while(m--){
        opt=read(); q=read(); x=read();
        if(opt==0) split(root[q],root[++tot],1,n,x,read()); // split_xy 
        else if(opt==1){root[q]=merge(root[q],root[x]);root[x]=0;} // 强制删除 
        else if(opt==2) change(root[q],1,n,read(),x);   
        else if(opt==3) printf("%lld\n",ask(root[q],1,n,x,read()));
        else{
            if(sum[root[q]]<x) puts("-1");
            else printf("%d\n",kth(root[q],1,n,x));
        }
    }
    return 0;
}

:::

例题 5

如果将上题中操作 0 改为：“将可重集 p 中值在 [x,y] 范围内的数，移动到可重集 t 中（t 原有元素保留）”，并删去合并操作，如何修改维护策略？

:::success[解法] 其实核心不变。我们依然先用两次分裂把 p 中 [x,y] 部分拆出来，得到一棵单独的树，然后将这棵树合并到 t 的线段树中。合并的均摊复杂度是 \mathcal{O}(\log n)，加上分裂也是 \mathcal{O}(\log n)，完全可以接受。这也说明，线段树分裂与合并结合，能灵活实现集合间的区间搬运，能力不输 FHQ-Treap 的分裂与合并，且在处理值域区间时更为直接。 :::

例题 6（如果强制在线呢！）

给定一个 1 \sim n 的排列，进行 m 次操作，每次操作将 [l, r] 区间内的数字按升序或降序排序。所有操作完成后，查询位置 p 上的数字是多少。

:::success[观察] 经典的离线做法是二分答案 x，将 \ge x 的数置为 1、其余置为 0，则区间排序转化为线段树区间赋值，单次判断 \mathcal{O}(m \log n)，总复杂度 \mathcal{O}(m \log^2 n)。

但如果题目要求强制在线，离线二分就不再适用。此时需要一种能够实时维护序列状态、处理任意区间排序并支持单点查询的数据结构。 :::

:::success[注意] 关键洞察在于：经过若干次排序操作后，序列会形成若干段连续的有序区间，每个区间内部已经升序或降序排列。初始时，每个位置自成一段。排序操作本质上就是将这些有序段合并成一个大的有序段，而当排序区间的端点不在段的边界上时，就需要将对应的有序段分裂开。

这正是线段树分裂与合并的用武之地。

我们从暴力的 "桶排序" 思路出发来理解。假设每个位置有一个桶，桶里放着该位置的数。

问题在于，某些桶可能已经在之前的排序中被合并到更大的桶中了。例如，[1,3] 已经升序排好放在了位置 1 的桶里，现在要对 [2,5] 排序 —— 我们需要把前 2 个元素从位置 1 的桶中 "拆" 出来，再把剩下的元素放回去。

桶的实现参照权值线段树。每个有序段用一棵动态开点的权值线段树来维护其内部的元素。维护段的左右端点、线段树根节点、以及升序 / 降序标记。我们需要一个支持快速查找的数据结构（如 set / 平衡树）来管理所有有序段。 :::

:::success[启示] 具体操作流程如下：

  1. 初始化：对每个位置 i 开一棵权值线段树，插入对应的元素 a_i。将 n 个长度为 1 的有序段插入 set 中。升序标记为 0，降序标记为 1。

  2. 分裂端点：对于排序区间的左右端点 l 和 r+1，在 set 中二分找到包含这些位置的有序段，将其在端点处分裂。分裂操作在权值线段树上按元素个数拆分：若为升序，直接按排名拆分；若为降序，则先颠倒左右子树的含义再拆分（因降序段中第 k 小的元素在线段树中对应的是第 \text{len}-k+1 个）。每次分裂的复杂度为 \mathcal{O}(\log n)，且至多新增 \mathcal{O}(\log n) 个节点。

  3. 合并：将端点之间（含端点本身）的所有完整有序段的权值线段树合并到左端点 l 上。升序时顺序合并，降序时倒序合并，并给 l 打上对应的升 / 降序标记。同时，从 set 中删除这些已被合并的段。

  4. 查询：对于查询位置 p，定位到其所在的有序段，在该段的权值线段树上查找第 k 小（k 为 p 在段内的偏移）。如果段是升序，第 k 小即为答案；如果段是降序，只需取第 \text{len}-k+1 小。

整个过程，每次操作均摊复杂度 \mathcal{O}(\log n)，总复杂度 \mathcal{O}((n+m)\log n)。总节点数为 \mathcal{O}((n+m)\log n)。

需要提醒的是：降序段的处理相比升序段要多一步下标映射，容易写错，需要格外注意。本题不支持值重复，因为排列保证了元素互异。

此题可解。 :::