一些约定：

• Past：自己看完后想了想就自己切掉的题
• Present：感觉有点难度或者属于某种没见过的套路的题
• Future：有一定思维难度/代码有点难写/使用了一些黑科技
• Beyond：思维难度较高/很难实现

一道经典题

先来看一道经典题目。

HEOI2016/TJOI2016 排序

给定一个长为 \(n\) 的排列，有 \(q\) 次操作。每次操作会将一个区间升序排序或降序排序，求最后序列中 \(p\) 位置上的数。\(1\le n,q\le 10^5\)。

众所周知我们可以二分最终的答案然后在线段树上做 \(q\) 次区间覆盖，这样复杂度就是 \(O((n+q)\log ^2n)\) 了。

不过实际上，本题可以做到 1log 的复杂度！而且还支持在线询问！

怎么做呢？这需要用到线段树的分裂与合并。

线段树合并

现在你有 \(n\) 个可重集 \(S_1,\cdots,S_n\)，每个可重集内的数的值域均为 \([1,m]\)。一开始，每个可重集内都只有一个数。

你要进行 \(q\) 次操作：

• 修改：选出两个可重集 \(S_i,S_j\)，并且将 \(S_i\) 设为 \(S_i\cup S_j\)，将 \(S_j\) 设为 \(\varnothing\)。
• 查询：询问第 \(i\) 个可重集内值在 \([l,r]\) 内的数的个数。

\(1\le n,q\le 4\times 10^5\)。

我们考虑对每个可重集维护一棵动态开点的权值线段树，那么查询就相当于一个区间求和。

现在需要处理合并操作。一个简单的方法是扫一遍 \(S_j\)，然后把 \(S_j\) 里面的每个节点都插进 \(S_i\)。

这样做很容易卡到 \(O(n^2)\) 次插入：依次对每个 \(i=1,2,\cdots,n\)，将 \(S_i\) 合并进 \(S_{i+1}\) 内。此时你发现这个算法就挂了。

你可能会想启发式合并；但这个东西复杂度是 2log 的，太逊了。

可以发现，如果两棵线段树维护的值域都是 \([1,m]\)，那么这两棵权值线段树对值域的划分应该也是一样的。如图：

图源 线段树合并：从入门到放弃

因此我们可以同步遍历这两棵线段树，对于每个节点，直接把 $S_j $ 的对应节点上的值合并到 \(S_i\) 上。

代码如下：

#define ls(p) (d[p].ls)
#define rs(p) (d[p].rs)

inline void pushup(int p){
    d[p].val=d[ls(p)].val+d[rs(p)].val;//d[p].val：节点 p 代表区间的区间和
}

inline int merge(int p,int q,int l,int r){
	if(!p||!q)return p^q;
	if(l==r){d[p].val+=d[q].val;return p;}
	int mid=(l+r)>>1;
	d[p].ls=merge(ls(p),ls(q),l,mid),d[p].rs=merge(rs(p),rs(q),mid+1,r);
	pushup(p);return p;
}

这样做的复杂度如何呢？

注意到我们会遍历到一个节点当且仅当这个节点同时存在于 \(p,q\) 所代表的树内。

也就是说，如果两棵树的叶子节点有 \(x\) 个重合的地方，那么合并这两棵树的复杂度就是 \(O(\min(n,x\log n))\)。

对于数 \(k\)，设其在所有可重集中出现次数为 \(c_k\)，那么可以发现它会被合并 \(c_k-1\) 次。一共只有 \(n\) 个数，因此，总的合并复杂度为 \(\sum_k (c_k-1)\log m=O(n\log m)\)。均摊下来，我们就可以将一次合并的复杂度看作 \(O(\log m)\)。

注意上述讨论只是在均摊意义下的讨论，单次线段树合并的复杂度完全可以到达 \(O(n)\)，只不过由于总的点数并不多，它们加起来复杂度不会超过 \(O(\min(m,n\log m))\)。

线段树合并-例题

CF600E Lomsat gelral Past 4

板子题。我们对树做一遍 dfs，然后对每个结点 \(u\)，依次递归它的每个子结点 \(v\)，然后把 \(v\) 那边建出的线段树合并到 \(\text{root}(u)\) 里面，再把 \(u\) 的颜色插入进去就行了。

很多人认为这题空间需要开到 \(O(n\log n)\)，然而真的如此吗？

实际上，注意到 \(c_i\le n\)，根据我们上面的讨论，空间开到 \(O(n)\) 就够了！

这需要我们在线段树合并的时候回收节点。如下：

inline void del(int p){
	d[p]=Node(0,0,0),b[++cnt]=p;
}
	
inline int build(){
	if(cnt>0)return b[cnt--];
	return ++tot;
}

inline int merge(int p,int q,int l,int r){
	if(!p||!q)return p^q;
	if(l==r){d[p].val+=d[q].val,del(q);return p;}
    int mid=(l+r)>>1;
	d[p].ls=merge(ls(p),ls(q),l,mid),d[p].rs=merge(rs(p),rs(q),mid+1,r);
	del(q),pushup(p);return p;
}

这样一来，空间复杂度就不会超过 \(O(n)\) 了。需要一些精细的实现。

AC Code

LuoguP4556 雨天的尾巴 Past 4

首先可以利用树上差分，对于一个 \(u,v,z\) 的链加操作，就相当于在 \(u,v\) 处 \(+z\)，在 \(\text{LCA}(u,v)\) 与 \(\text{Father}(\text{LCA}(u,v))\) 处 \(-z\)。

那么现在每个点上的信息就变成了一个子树和，然后就和上题一模一样了=_= AC Code

线段树分裂

还是有 \(n\) 个可重集 \(S_1,S_2,\cdots,S_n\)，一开始每个可重集内只有一个数。有 \(q\) 次操作：

• 修改：选出两个可重集 \(S_i,S_j\)，并且将 \(S_i\) 设为 \(S_i\cup S_j\)，将 \(S_j\) 设为 \(\varnothing\)。
• 查询：询问第 \(i\) 个可重集内值在 \([l,r]\) 内的数的个数。

现在我们添加一种修改操作：

• 修改2：选出两个可重集 \(S_i,S_j\)，给定 \(k\)，你需要将 \(S_i\) 中前 \(k\) 小的数拿出来，然后放进 \(S_j\) 里面。保证 \(|S_i|\ge k\)。

仍然考虑用权值线段树来维护每个可重集。

对于修改2，考虑先新建一棵线段树 \(T\)，将 \(S_i\) 中的前 \(k\) 小扔到 \(T\) 里面，再把 \(T\) 和 \(S_j\) 合并。

问题在于怎么把 \(S_i\) 中的前 \(k\) 小扔到 \(T\) 里面。

如图，\(k=6\)，我们将左边的线段树分成了右边两棵。

考虑从根开始遍历这棵线段树。

类似于经典的求区间第 \(k\) 小的操作，我们设左子树所代表区间中的数的数量为 \(x\)：

• \(x>k\)，那么右子树全都归 \(S_i\) 不会变，往左侧递归即可。
• \(x=k\)，那么左子树归 \(T\)，右子树归 \(S_i\)。
• \(x，那么左子树全都归 \(T\)，将 \(k\) 减去 \(x\)，往右侧递归即可。

void split(int p,int &q,int k){
	q=build();int v=d[ls(p)].val;
	if (k>v)split(rs(p),rs(q),k-v);
	else rs(q)=rs(p),rs(p)=0;
	if (k

分析一波复杂度：每次只会递归 \(O(\log n)\) 层，因此复杂度为 \(O(\log n)\)。

实际上从上面那个图也可以看出来，新建的节点其实就是两部分重合的那一条链，因此时空复杂度都是 \(O(\log n)\)。

线段树分裂-例题

LuoguP5494 【模板】线段树分裂

对每个可重集维护一棵权值线段树，那么操作就是分裂、合并、单点加、区间求和、全局第 \(k\) 小。

这题要求把值在 \([l,r]\) 范围内的数分裂出去，其实也差不多。

从根节点开始往下递归，设当前节点为 \(p\)，其代表区间为 \(L_p,R_p\)，分裂的值域为 \([l,r]\)，那么：

• \([L_p,R_p]\) 被 \([l,r]\) 包含。那么这一整颗子树都要归新的线段树。
• \([L_p,R_p]\) 与 \([l,r]\) 完全没有交集。那么可以直接 return。
• \([L_p,R_p]\) 与 \([l,r]\) 相交，但不被它包含。那么这个节点的一部分归自己，一部分归那一棵新树，因此两棵树中都会有这个节点。所以需要新建一个节点，同时往左右子树递归下去。

可以发现这和我们普通线段树的区间操作基本一样，所以复杂度是 \(O(\log n)\)。

AC Code

题目选讲

LuoguP3521 POI2011 ROT-Tree Rotations Future 7.5

可以发现，自己子树内的点无论交换不交换，对自己子树外面的点的贡献是一定的。

因此可以考虑贪心，自底向上遍历节点，如果交换后逆序对个数变少就换一下。

现在只需要快速算出来交换后逆序对数量是否变小。

一个想法是归并排序：在每个节点上存一个 vector，遍历的时候把左右子树归并起来，在归并的时候顺便统计一下。这样，如果设 \(f_u\) 为 \(u\) 子树内叶子节点的个数，那么复杂度为 \(O(\sum f_u)\)。

然而很容易卡到 \(O(n^2)\)：考虑下面这棵树

此时 \(\sum f_u=O(n^2)\)，这个算法就挂了。

一个想法是启发式合并：对每颗子树内的叶子节点维护一颗权值线段树之类的东西，然后每次合并两个儿子时把 size 较小的一个一个插入进 size 较大的：设插入的数为 \(x\)，我们查询 \(< x\) 的元素个数与 \(>x\) 的元素个数就能算出来合并之后新增的逆序对数了。

然而这样的话复杂度为 \(O(n\log ^2n)\)，非常的 naive

其实可以发现线段树合并的时候，设当前节点为 \(p,q\)，如果把 \(p\) 放在前面，那么此时左子树内的所有节点都小于右子树内的节点。也就是说，新增的逆序对个数其实就是 siz[ls(p)]*siz[rs(q)]。

因此，我们可以在线段树合并的时候，直接算出来新增的逆序对数。这样复杂度就是 \(O(n\log n)\) 了。

2020 CCPC Wannafly Winter Camp Day2 E Future 7.0

请把 \(1\le n\le 10^5\) 改为 \(1\le n\le 5\times 10^5\) QAQ

类似上题，我们可以用一个 std::multiset 来维护有序对，然后启发式合并。

这样的复杂度是 \(O(n\log ^2n)\)，非常的 naive。貌似这就是标算的做法了

考虑线段树合并：在值域上开线段树，然后每个节点上维护最左端和最右端的数 \(L(u),R(u)\)，以及该节点的答案。

那么 pushup 是很好做的。考虑怎么合并。

设当前合并的是节点 \(p\) 和 \(q\)，那么只需要把 \(R(\text{lson}(p)),R(\text{lson}(q)),L(\text{rson}(p)),L(\text{rson}(q))\) 四个数拉出来比一比大小，然后加上贡献就可以了。复杂度 \(O(n\log n)\)，把 std 吊着打。AC Code

LuoguP5612 【Ynoi2013】Ynoi Future 9.6

重点来看区间排序的操作。

我们发现，当我们对一个区间进行排序的时候，这一整个区间就变成了有序的。听君一席话

这个东西其实和区间覆盖非常相似。

那么我们就可以使用珂朵莉树来维护极长的有序段的左右端点，每次操作的时候分裂出对应的区间，再把它们都合并起来就行了。

如何实现分裂与合并呢？考虑使用权值线段树。分裂的时候就相当于把前 \(k\) 小分裂出来，合并就相当于合并两个权值线段树。

这样做的复杂度如何呢？我并不会分析QAQ，不过思考一下可以发现分裂的复杂度是严格的 \(O(\log n)\)，合并的复杂度是 \(O(\text{两个线段树相交部分})\)，而类似于珂朵莉树的分析我们知道极长连续有序段个数是很少的，所以复杂度看起来还可以？

本题中需要支持全局异或&全局异或和，那么使用一个 Trie 就可以了。Trie 本质上就是动态开点的权值线段树，因此同样可以进行合并与分裂。时间复杂度 \(O((n+q)\log V)\)。然而本题非常卡常，我并没能卡过去。。

到这里你可以发现，我们一开始说的那个题就是区间排序的板子题=_= 直接做就可以了。\(O((n+q)\log n)\)。