【平衡树总结 Ⅲ】【FHQ Treap】非旋Treap |【CGWR③】| E

闭关了一周，终于可以正面对刚淑芬啦 qwq，刷分成功√

接下来就好好补题填坑吧…

平衡树总结Ⅲ：FHQ Treap

(一) 概述

说 FHQ Treap 前，先来说说 Treap 吧：

T r e a p Treap Treap 的结点有些特别。每个结点除了左右孩子指针域、子树大小域等辅助域外，还有两个关键数值域：数据域和权重域。其中数据域就用来存放我们想存的数据，而权重域则用来维护堆性质。

T r e a p = B S T + H e a p Treap = BST + Heap Treap=BST+Heap，从名字就可以看出来它同时满足二者性质。一棵 T r e a p Treap Treap，其结构对于数据域满足二叉排序树的性质；对于权重域满足小（大）根堆的性质。

那么为什么 T r e a p Treap Treap 能够实现自平衡呢？我们都知道，最最朴素的 B S T BST BST 在数据随机的情况下表现非常好，那么在面对更常见的 更丧心病狂 的数据时，我们有没有什么办法可以实现“随机化”呢？ T r e a p Treap Treap 就做到了这一点，因为它结点的权重域的值是随机钦定的。

为什么这样就能实现平衡呢？我们先考虑一棵普通的二叉搜索树，假设其在旋转操作（不破坏中序遍历有序性）下所能变换的结构的全集是 { S } \{S\} {S}。然后我们在 { S } \{S\} {S} 中等概率地随机选一种结构，感性地感受一下，选中的这棵树是非常糟糕的链状结构的概率会

很低

，而大多数情况下它的形状都还比较平衡。

那 T r e a p Treap Treap 是怎么做的呢？我们再把刚才那棵普通的二叉搜索树和其变换全集 { S } \{S\} {S} 拿过来，我们把它每个结点都随机加上一个附加权值，然后在 { S } \{S\} {S} 中逐个检查其结构对于这个权值域是否能满足堆性质（必至少会有一种结构满足堆性质，详细证明大家可以查阅相关论文）。记能满足性质的结构的集合是 { Q } \{Q\} {Q}（能显然感觉到的是， { Q } \{Q\} {Q} 中元素个数是远小于 { S } \{S\} {S} 的），那么从这里面再随便挑一个，就成为了 T r e a p Treap Treap 的当前结构。

所以大多数情况下 T r e a p Treap Treap 的形状都是比较平衡的。理论上可证明其高度的数学期望是 O ( log ⁡ ( n ) ) O(\log(n)) O(log(n)) 的。

而具体编程的时候，我们显然不能像上面那样选出结构… 实际上是这样做的：当树结构必须发生改变（增删结点）的时候，我们先按满足 B S T BST BST 性质的方式去做，做完之后再检查是否破坏堆性质了，如果破坏了我们就用旋转操作去维护，使其重新满足堆性质（由于是靠旋转操作维护，所以不用担心维护着维护着又把 B S T BST BST 性质给破坏了）

然后我们再回到 FHQ Treap：

那么我们在增删结点的时候能不能 同时不破坏BST和堆 的性质呢？这样就不用旋转了呀。

FHQ 大神告诉了我们答案：可以！

现在提供三种核心操作：（记结点数据域是 v a l val val，权重域是 w e i g h t weight weight）

• ① 合并： 把两棵小 T r e a p Treap Treap   x x x 和 y y y（ ∀   n o d e 1 ∈ x ， n o d e 2 ∈ y \forall \ node_1 \in x，node_2 \in y ∀ node1​∈x，node2​∈y，都满足 x . v a l < y . v a l x.val < y.val x.val<y.val）合并成一棵新的大 T r e a p Treap Treap
• ② 按数值分裂： 把一棵大 T r e a p Treap Treap 按照某个指定数值 k e y key key 分成两棵小 T r e a p Treap Treap   x x x 和 y y y，且 ∀   n o d e 1 ∈ x ， n o d e 2 ∈ y \forall \ node_1 \in x，node_2 \in y ∀ node1​∈x，node2​∈y，都满足 x . v a l ≤ k e y < y . v a l x.val \le key < y.val x.val≤key<y.val
• ③ 按规模分裂： 把一棵大 T r e a p Treap Treap 按照某个指定规模 k k k 分成两棵小 T r e a p Treap Treap   x x x 和 y y y，其中 x x x 的结点数 恰为 k k k，且 ∀   n o d e 1 ∈ x ， n o d e 2 ∈ y \forall \ node_1 \in x，node_2 \in y ∀ node1​∈x，node2​∈y，都满足 x . v a l < y . v a l x.val < y.val x.val<y.val

那么靠这三种核心操作就可以在 同时不破坏BST和堆 的性质的前提下进行增删结点操作了！

甚至还支持更多操作（查询排名、查询前驱后继、查询第 k k k 大、维护区间进行区间翻转、可持久化等等…）

那具体怎么实现 FHQ Treap 呢？

下面马上详细剖析 F H Q    T r e a p FHQ\ \ Treap FHQ  Treap 的各个操作。

(二) 三个核心操作分析

① 合并

共有以下三种情况：

• 1.若左子树为空，则右子树就是合并后的树；若右子树为空，则左子树就是合并后的树；若都为空那么随便指定皆可。

  

• 2.左子树根的权重值 < < < 右子树根的权重值，那么合树根必为左子树根。然后合并左子树的右子树 和 右子树，合并后挂在左子树的右孩子指针上（覆盖掉该指针的旧值）：

  

  

  

• 3.左子树根的权重值 ≥ \ge ≥ 右子树根的权重值，那么合树根必为右子树根。然后合并左子树 和 右子树的左子树，合并后挂在右子树的左孩子指针上（覆盖掉该指针的旧值）。和第二种情况同理，就不附图了。

然后来个稍复杂的合并的图例：

看起来很复杂？不不不… 由于存在递归和引用类型参数，代码其实是相当简洁而对称的：

void merge(Node *&rt, Node *l, Node *r)	// 合并左树l和右树r，合并后的树根将赋值给rt指针引用
{
	if (l == NIL)		// 情况1的第一种子情况：左树l空，新根必为右树r
		rt = r;
	else if (r == NIL)	// 情况1的第二种子情况：右树r空，新根必为左树l
		rt = l;
	else if (l->w < r->w)
		rt = l, merge(l->rc, l->rc, r), pu(rt);	// 情况2：l权重小，新根必为l，然后还需递归合并l的右子树 和 r，合并形成的新子树是l的新右子树
	else
		rt = r, merge(r->lc, l, r->lc), pu(rt);	// 情况2：r权重小，新根必为r，然后还需递归合并l 和 r的左子树，合并形成的新子树是r的新左子树
}

           

那么这就是合并操作了，是不是很漂亮又简单呢。

② 按数值分裂

按值（记这个值是 k e y key key）分裂呢也是有三种情况：（记待分裂树根是 r t rt rt，待生成的左右子树根分别是 l l l 和 r r r）

• 1.如果 r t rt rt 是空，那么显然分裂成的左右子树都是空树。
• 2.如果 r t → v a l rt\rightarrow val rt→val （注意不是 r t → w e i g h t rt \rightarrow weight rt→weight） ≤ k e y \le key ≤key，那么显然 r t rt rt 自身和其整个左子树的值都 ≤ k e y \le key ≤key，所以待生成的 l l l 必定指向 r t rt rt 自身。然后我们需要递归地把 r t rt rt 的右子树给分裂一下，使其分裂出一块值恰 > k e y > key >key 的子树，然后把这个子树从 r t rt rt 上剥离下来，再把其根的值赋给 r r r，这样就完成了。下面是图例（假设 k e y = 5 key = 5 key=5）

  

• 3.如果 r t → v a l > k e y rt\rightarrow val > key rt→val>key，那么显然 r t rt rt 自身和其整个右子树的值都 > k e y > key >key，所以待生成的 r r r 必定指向 r t rt rt 自身。然后我们需要递归地把 r t rt rt 的左子树给分裂一下，使其分裂出一块值恰 ≤ k e y \le key ≤key 的子树，然后把这个子树从 r t rt rt 上剥离下来，再把其根的值赋给 l l l，这样就完成了。这和情况2是完全对称的，因此不再举例。

看起来也很复杂？不不不… 由于存在递归和引用类型参数，代码也是相当简洁而对称的啦：

// value-based-split
int vv;

void split(Node *rt, Node *&l, Node *&r)	// 待分裂树根是rt，待生成的左右子树根分别是l和r，将rt分为l和r两棵子treap，分裂后要使l的所有结点的val皆 <= vv，r的所有结点的val皆 > vv
{
	if (rt == NIL)			// 情况1：rt是空，那么显然分裂成的左右子树也都是空
		l = r = NIL;
	else if (rt->v <= vv)	// 情况2：rt->v<=vv，那么l=rt，然后递归地把rt的右子树给分裂一下，使其分裂出一块值恰> key的子树，然后把这个子树从rt上剥离下来，再把其根的值赋给r
		l = rt, split(rt->rc, rt->rc, r), pu(rt);
	else					// 情况3：rt->v> vv，那么r=rt，然后递归地把rt的左子树给分裂一下，使其分裂出一块值恰<=key的子树，然后把这个子树从rt上剥离下来，再把其根的值赋给l
		r = rt, split(rt->lc, l, rt->lc), pu(rt);
}
           

而且这个代码是不是和合并函数的代码非常像？？连递归传参都是一样的！

③ 按规模分裂

基本上和按值分裂没差。

按规模（记给定规模是 k k k）分裂有四种情况：（记待分裂树根是 r t rt rt，待生成的左右子树根分别是 l l l 和 r r r）

• 1.如果 r t rt rt 是空，那么显然分裂成的左右子树都是空树。
• 2.如果 k = = 0 k==0 k==0，那不用再分了，整棵树全部分到右边，直接给 l l l 赋空值，然后 r = r t r=rt r=rt。
• 3.如果 1 + r t → s i z e ≤ k 1+rt\rightarrow size \le k 1+rt→size≤k，那么说明 r t rt rt 自身和其整个左子树的数目加起来还不一定够 k k k 这么多，所以待生成的 l l l 必定指向 r t rt rt 自身，然后还需从 r t rt rt 的右子树上再找 v a l val val 最小的 k − r t → s i z e − 1 k-rt\rightarrow size-1 k−rt→size−1 个结点也算作 l l l 的，其余的再剥离，然后把剥离后的子树的根的地址赋给 r r r，就完成分裂了。
• 4.如果 1 + r t → s i z e > k 1+rt\rightarrow size > k 1+rt→size>k，那么说明 r t rt rt 自身和其整个左子树的数目加起来就超过 k k k 了，所以待生成的 r r r 必定指向 r t rt rt 自身，然后得从 r t rt rt 的左子树上找 v a l val val 最小的 k k k 个结点，然后把它们剥离出来，把剥离后的子树的根的地址赋给 l l l，就完成分裂了。

图就不再附啦~ 按规模分裂和按值分裂的唯一区别就是按规模分裂多了一种 k = = 0 k==0 k==0 的情况。代码也几乎是一样的：

// size-based-split
void split(Node *rt, Node *&l, Node *&r, const xint k)	// 待分裂树根是rt，待生成的左右子树根分别是l和r，将rt分为l和r两棵子treap，使得l的大小恰是k，且l的任意结点的val皆 < r的任意结点的val
{
	if (rt == NIL)			// 情况1：rt是空，那么显然分裂成的左右子树也都是空
		l = r = NIL;
	else if (k == 0)		// 情况2：k==0，那不用再分了，整棵树全部分到右边，直接给l赋空值，然后r=rt
		l = NIL, r = rt;
	else if (rt->lc->sz+1 <= k)	// 情况3：rt->lc->sz+1 <= k，那么说明rt自身和其整个左子树的数目加起来还不一定够k这么多，所以待生成的l必定指向rt自身，然后还需从rt的右子树上再找val最小的k - rt->lc->sz -1个结点也算作l的，其余的再剥离，然后把剥离出的树的根的地址赋给r，就完成分裂了
		l = rt, split(rt->rc, rt->rc, r, k-rt->lc->sz-1), pu(rt);
	else						// 情况4：rt->lc->sz+1 >  k，那么说明rt自身和其整个左子树的数目加起来就超过k了，所以待生成的r必定指向rt自身，然后得从rt的左子树上找val最小的k个结点，然后把它们剥离出来，把剥离后的子树的根的地址赋给l，就完成分裂了
		r = rt, split(rt->lc, l, rt->lc, k), pu(rt);
}
           

那么有了这三个核心操作后，就可以由他们派生出一系列功能操作了。

(三) 七个核心操作分析

① 插入数据值为 v 、权重值随机给定的一个新结点

• 把大 T r e a p Treap Treap 按数值 v v v 分裂为 左子树 l l l 和 右子树 r r r，然后合并 l l l 和 新结点，然后再合并 l l l 和 r r r

② 删除数据值为 v 的一个结点

• 把大 T r e a p Treap Treap 按数值 v v v 分裂为 左子树 l l l 和 右子树 r r r，然后再把左子树 l l l 按数值 v − 1 v-1 v−1 分裂为左子树 l l l 和中子树 m m m（这样就使得 m m m 的所有结点的 v a l val val 均等于 v v v），然后合并 m m m 的左右子树使其成为新的 m m m（此步相当于删除了 m m m 的根结点），然后再合并 l l l 和 m m m，然后再合并 l l l 和 r r r，即可完成删除。

③ 求 v 的最小排名，即树中比 v 小的数的个数+1

• 把大 T r e a p Treap Treap 按数值 v − 1 v-1 v−1 分裂为 左子树 l l l 和 右子树 r r r，然后记下此时左子树的大小为 s i z e size size，合并 l l l 和 r r r，然后返回 s i z e + 1 size+1 size+1 即可。

④ 求 v 的最大排名，即树中 ≤ \le ≤ v 的个数

• 把大 T r e a p Treap Treap 按数值 v v v 分裂为 左子树 l l l 和 右子树 r r r，然后记下此时左子树的大小为 s i z e size size，合并 l l l 和 r r r，然后直接返回 s i z e size size 即可。

⑤ 求树中排名为 k 的值

• 把大 T r e a p Treap Treap 按规模 k k k 分裂为 左子树 l l l 和 右子树 r r r，然后记下此时左子树中最大的结点。合并 l l l 和 r r r，然后返回这个最大结点的数据值即可。

⑥ 求值 v 的前驱值，即树中比 v 小的最大值

• 把大 T r e a p Treap Treap 按数值 v − 1 v-1 v−1 分裂为 左子树 l l l 和 右子树 r r r，然后记下此时左子树中最大的结点。合并 l l l 和 r r r，然后返回这个最大结点的数据值即可。

⑦ 求值 v 的后继值，即树中比 v 大的最小值

• 把大 T r e a p Treap Treap 按数值 v v v 分裂为 左子树 l l l 和 右子树 r r r，然后记下此时右子树中最小的结点。合并 l l l 和 r r r，然后返回这个最小结点的数据值即可。

都说 替罪羊树 是暴力美学，可我觉得 FHQ Treap 才是最漂亮的暴力美学。FHQ Treap 仅通过 merge 和 split 的各种巧妙组合，就完成了平衡树的任意操作，实在是高妙！

(四) 例题

1.   洛谷P3369 【模板】普通平衡树

直接实现 FHQ Treap 的各个基本功能即可。

值得注意的一点是，可以给整棵树加一个实际存在的空节点 _ N I L \_NIL _NIL，并用其地址作为 N I L NIL NIL 代替 n u l l p t r nullptr nullptr，以减少特判次数和coding出错几率。（这招在《算导》红黑树那一章也有所采用，不过这里主要还是从虎鸽鸽的std那里学来的~）

#include <cstdio>
#include <random>


constexpr int MN(1e5+7);


template<typename vint>
class FHQ
{
private:

	using xint = int;
	using ring = unsigned long;

	std::mt19937 rander;

	struct Node
	{
		Node *lc, *rc;
		vint v;
		ring w;
		xint sz;
	} _pool[MN], *pool = _pool;
	Node _NIL = {&_NIL, &_NIL, 0, 0, 0}, *NIL = &_NIL;
	Node *root = NIL;
	Node *new_node(const vint v)
	{
		return *++pool = {NIL, NIL, v, rander(), 1}, pool;
	}
	int vv;

#define pu(p) \
	({ \
		p->sz = p->lc->sz + p->rc->sz + 1; \
	})
#define min_node(rt) \
	({ \
		Node *__p = rt; \
		while (__p->lc != NIL) \
			__p = __p->lc; \
		__p; \
	})
#define max_node(rt) \
	({ \
		Node *__p = rt; \
		while (__p->rc != NIL) \
			__p = __p->rc; \
		__p; \
	})

	void merge(Node *&rt, Node *l, Node *r)
	{
		if (l == NIL)
			rt = r;
		else if (r == NIL)
			rt = l;
		else if (l->w < r->w)
			rt = l, merge(l->rc, l->rc, r), pu(rt);
		else
			rt = r, merge(r->lc, l, r->lc), pu(rt);
	}

	// value-based-split
	void split(Node *rt, Node *&l, Node *&r)
	{
		if (rt == NIL)
			l = r = NIL;
		else if (rt->v <= vv)
			l = rt, split(rt->rc, rt->rc, r), pu(rt);
		else
			r = rt, split(rt->lc, l, rt->lc), pu(rt);
	}

	// size-based-split
	void split(Node *rt, Node *&l, Node *&r, const xint k)
	{
		if (rt == NIL)
			l = r = NIL;
		else if (k == 0)
			l = NIL, r = rt;
		else if (rt->lc->sz+1 <= k)
			l = rt, split(rt->rc, rt->rc, r, k-rt->lc->sz-1), pu(rt);
		else
			r = rt, split(rt->lc, l, rt->lc, k), pu(rt);
	}

public:

	FHQ(void) : rander(19937) { }

	void clear(void)
	{
		root = NIL;
		pool = _pool;
	}

	void insert(const vint v)
	{
		Node *l, *r;
		vv = v;
		split(root, l, r);	// value-based-split
		merge(l, l, new_node(v));
		merge(root, l, r);
	}

	void erase(const vint v)
	{
		Node *l, *m, *r;
		vv = v;
		split(root, l, r);	// value-based-split
		vv = v-1;
		split(l, l, m);		// value-based-split
		merge(m, m->lc, m->rc);
		merge(l, l, m);
		merge(root, l, r);
	}

	xint lw_rank(const vint v)
	{
		Node *l, *r;
		vv = v-1;
		split(root, l, r);	// value-based-split
		xint less_cnt = l->sz;
		merge(root, l, r);
		return less_cnt + 1;
	}

	xint up_rank(const vint v)
	{
		Node *l, *r;
		vv = v;
		split(root, l, r);	// value-based-split
		xint leq_cnt = l->sz;
		merge(root, l, r);
		return leq_cnt;
	}

	vint nth(const xint k)
	{
		Node *l, *r;
		split(root, l, r, k);// size-based-split
		Node *pmax = max_node(l);
		merge(root, l, r);
		return pmax->v;
	}

	vint prev(const vint v)
	{
		Node *l, *r;
		vv = v-1;
		split(root, l, r);	// value-based-split
		Node *pmax = max_node(l);
		merge(root, l, r);
		return pmax->v;
	}

	vint next(const vint v)
	{
		Node *l, *r;
		vv = v;
		split(root, l, r);	// value-based-split
		Node *pmin = min_node(r);
		merge(root, l, r);
		return pmin->v;
	}
};


FHQ<int> t;


int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int op, v;
		scanf("%d %d", &op, &v);
		switch (op)
		{
			case 1:
				t.insert(v);
				break;
			case 2:
				t.erase(v);
				break;
			case 3:
				printf("%d\n", t.lw_rank(v));
				break;
			case 4:
				printf("%d\n", t.nth(v));
				break;
			case 5:
				printf("%d\n", t.prev(v));
				break;
			case 6:
				printf("%d\n", t.next(v));
				break;
		}
	}

	return 0;
}

           

2.   洛谷P3391 【模板】文艺平衡树

FHQ Treap 还能维护区间，特别是可以实现 区间翻转！（通过按规模分裂找到应该翻转的区段，然后直接交换左右孩子指针即可）

记得维护懒标记，否则可能会 T \text{T} T 掉。

【CGWR】① ：这种带懒标记的平衡树，在 dfs \text{dfs} dfs 的时候很容易忘记先 push_down \text{push\_down} push_down 再 dfs \text{dfs} dfs 子树！！要特别注意！！

【CGWR】② ：用笛卡尔建树的方法给作为区间树的 FHQ Treap \text{FHQ Treap} FHQ Treap 建树时，借用了 NIL \text{NIL} NIL 作为哨兵，所以一定要注意在最后记录 NIL \text{NIL} NIL 的 rc \text{rc} rc 为 root \text{root} root，然后再把 rc \text{rc} rc 重置为 NIL \text{NIL} NIL！

#include <cstdio>

#define SWAP(a, b) do{auto __tp=a; a=b; b=__tp;}while(0)

using rint = unsigned long;
rint __r_ = 0xbadf00d;
#define rander() (__r_+=__r_<<2u|1u)


constexpr int MN(1e5+5);

template <typename vint>
class FHQ
{
private:

	using xint = int;

	struct Node
	{
		Node *lc, *rc;
		vint v;
		rint w;
		xint sz;
		bool reved;

		void rev()
		{
			reved = !reved;
			SWAP(lc, rc);
		}

		void pu()
		{
			sz = 1 + lc->sz + rc->sz;
		}

		void pd()
		{
			if (reved)
			{
				lc->rev(), rc->rev();
				reved = false;
			}
		}
	} _pool[MN], *pool = _pool;
	Node _NIL = {&_NIL, &_NIL, 0, 0, 0, false}, *NIL = &_NIL;
	Node *root = NIL;
	Node *sta[MN];
	Node *new_node(const vint v)
	{
		return *++pool = {NIL, NIL, v, rander(), 1, false}, pool;
	}

	void mg(Node *&rt, Node *l, Node *r)
	{
		if (l == NIL)
			rt = r;
		else if (r == NIL)
			rt = l;
		else if (l->w < r->w)
			rt = l, rt->pd(), mg(rt->rc, rt->rc, r), rt->pu();
		else
			rt = r, rt->pd(), mg(rt->lc, l, rt->lc), rt->pu();
	}

	void sp(Node *rt, Node *&l, Node *&r, const xint k)
	{
		if (rt == NIL)
			l = r = NIL;
		else if (k == 0)
			l = NIL, r = rt;
		else if (rt->lc->sz+1 <= k)
			l = rt, rt->pd(), sp(rt->rc, rt->rc, r, k-rt->lc->sz-1), rt->pu();
		else
			r = rt, rt->pd(), sp(rt->lc, l, rt->lc, k), rt->pu();
	}

public:

	void build(const xint n)
	{
		int top = 0;
		sta[top] = NIL;
		for (int i=1; i<=n; ++i)
		{
			Node *p = new_node(i);
			while (sta[top]->w > p->w)
				p->lc = sta[top], sta[top--]->pu();
			sta[top]->rc = p;
			sta[++top] = p;
		}

		while (top)
			sta[top--]->pu();
		root = NIL->rc, NIL->rc = NIL;
	}

	void rev(const xint l, const xint r)
	{
		Node *x, *y, *z;
		sp(root, x, y, l-1);
		sp(y, y, z, r-l+1);
		y->rev();
		mg(y, y, z);
		mg(root, x, y);
	}

	void dfs(Node *p)
	{
		if (p != NIL)
			p->pd(), dfs(p->lc), printf("%d ", p->v), dfs(p->rc);
	}
	void dfs(void)
	{
		dfs(root);
	}
};


FHQ<int> t;

int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	t.build(n);

	while (k--)
	{
		int l, r;
		scanf("%d %d", &l, &r);
		t.rev(l, r);
	}
	t.dfs();

	return 0;
}

           

3.   CODEVS 4655. 序列终结者

把 FHQ Treap \text{FHQ Treap} FHQ Treap 当区间树使的典型例子。

易错点 还是和上一题一样，不要忘记下传标记和笛卡尔建树时最后的操作。

个人感觉 FHQ Treap \text{FHQ Treap} FHQ Treap 还是很快的，下面这份代码以 2110 ms \text{2110 ms} 2110 ms 拿到了速度的 rk1 \text{rk1} rk1。

【CGWR】③ 这里还有一个易错的地方：写 split \text{split} split 函数的时候常常会 复制 merge \text{merge} merge 函数的代码然后再改。但是有时候会忘记改参数的引用类型。但是这个时候编译指令

Wuninitialized

就会派上用场了，就能够起到提醒的作用。

为什么呢？因为在功能函数中我们必然会写 “Node *x, *y, *z;” 这样的代码，然后再 sp 它们。如果我们忘了改 sp 的参数的引用类型（忘了在第二个和第三个类型上加引用），那么编译器会认为 x、y、z 它们没有被初始化！而如果没忘，那么由于我们把 x、y、z 已经以引用方式传递过了，就不会产生警告。

所以遇见这种警告千万不要忽视。这正是 sp 函数参数类型错误的提示，赶快去改代码。

附图：

/* CODEVS.4655 序列终结者
http://codevs.cn/problem/4655/

FHQ 实现区间树（笛卡尔建树、区间加、区间最值、区间翻转）

*/

#include <cstdio>
#include <climits>
#define _BS 1048576
char _bf[_BS];
char *__p1=_bf,*__p2=_bf;
#define _IO char *_p1=__p1,*_p2=__p2;
#define _OI __p1=_p1,__p2=_p2;

#ifdef _KEVIN
#define GC getchar()
#else
#define GC (_p1==_p2&&(_p2=(_p1=_bf)+fread(_bf,1,_BS,stdin),_p1==_p2)?EOF:*_p1++)
#endif

#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)
#define _G1(_1) int _1;sc(_1)
#define _G2(_1,_2) int _1,_2;sc(_1)sc(_2)
#define _G3(_1,_2,_3) int _1,_2,_3;sc(_1)sc(_2)sc(_3)
#define _gG(_1,_2,_3,_get, ...) _get
#define get(...) _gG(__VA_ARGS__,_G3,_G2,_G1, ...)(__VA_ARGS__)
#define F(i,l,r) for(int i=(l);i<(r);++i)

template<class T>
void PRT(const T _){if(_<0){PC(45),PRT(-_);return;}if(_>=10)PRT(_/10);PC(_%10+48);}

#define MAX(a, b) ((a)>(b)?(a):(b))
#define SWAP(T, a, b) do{T __tp=a; a=b; b=__tp;}while(0)

const int MN = 5e4+7;
typedef unsigned long rint;
rint __r_ = 0xbadf00d;
#define rander() (__r_+=__r_<<2u|1u)


template <typename vint, typename sint>
class FHQ
{
private:

#define SINT_MIN INT_MIN

	typedef int xint;

	struct Node
	{
		Node *lc, *rc;
		sint v, max, inc_lz;
		rint w;
		xint sz;
		bool reved;

		void rev(void)
		{
			reved = !reved;
			SWAP(Node*, lc, rc);
		}

		void inc(const vint d)
		{
			if (sz)	// 【CGWR】这里要加特判，以防止NIL结点的max被改动。NIL结点的max应始终为SINT_MIN！
				v += d, max += d, inc_lz += d;
		}

		void pu(void)
		{
			max = MAX(v, MAX(lc->max, rc->max));
			sz = 1 + lc->sz + rc->sz;
		}

		void pd(void)
		{
			if (reved)
			{
				lc->rev(), rc->rev();
				reved = false;
			}
			if (inc_lz)
			{
				lc->inc(inc_lz), rc->inc(inc_lz);
				inc_lz = 0;
			}
		}
	} _pool[MN], *pool;
	Node _NIL, *NIL, *root;
	Node *new_node(const vint v)
	{
		return *++pool = (Node){NIL, NIL, v, v, 0, rander(), 1, false}, pool;
	}
	Node *sta[MN];	// 用于建笛卡尔树的单调栈（w递增），栈中存当前树的最右链

	void mg(Node *&rt, Node *l, Node *r)
	{
		if (l == NIL)
			rt = r;
		else if (r == NIL)
			rt = l;
		else if (l->w < r->w)
			rt = l, rt->pd(), mg(rt->rc, rt->rc, r), rt->pu();
		else
			rt = r, rt->pd(), mg(rt->lc, l, rt->lc), rt->pu();
	}

	void sp(Node *rt, Node *&l, Node *&r, const xint k)
	{
		if (rt == NIL)
			l = r = NIL;
		else if (k == 0)
			l = NIL, r = rt;
		else if (rt->lc->sz+1 <= k)
			l = rt, rt->pd(), sp(rt->rc, rt->rc, r, k-rt->lc->sz-1), rt->pu();
		else
			r = rt, rt->pd(), sp(rt->lc, l, rt->lc, k), rt->pu();
	}

public:

	FHQ(void) :
		pool(_pool),
		NIL(&_NIL),
		root(NIL)
	{
		_NIL = (Node){NIL, NIL, SINT_MIN, SINT_MIN, 0, 0, 0, false};
	}

	void build(xint n)	// 每个点只会出栈一次，复杂度是O(n)的，且出栈的同时需要pushup（出栈时其子树必构造完毕）
	{
		int top = 0;
		sta[top] = NIL;	// 建树需要借用NIL作为哨兵
		while (n--)
		{
			Node *p = new_node(0);		// 本题，序列的每个元素的初值都是0
			while (sta[top]->w > p->w)	// 不用担心top会掉到0以下，因为哨兵在0，挡住了
				p->lc = sta[top], sta[top--]->pu();
			sta[top]->rc = p;
			sta[++top] = p;
		}

		while (top)		// 栈底的NIL不需要pushup，不然待会又要修正它的其他域
			sta[top--]->pu();
		root = NIL->rc;	// 建树借用了NIL，NIL的rc被修改（其他域都不变）为树的真实的根，记一下这个根
		NIL->rc = NIL;	// 然后再恢复NIL的rc为NIL
	}

	void inc(xint l, xint r, const vint v)
	{
		if (l > r)
			SWAP(xint, l, r);
		Node *x, *y, *z;
		sp(root, x, y, l-1);
		sp(y, y, z, r-l+1);
		y->inc(v);
		mg(y, y, z);
		mg(root, x, y);
	}

	void rev(xint l, xint r)
	{
		if (l > r)
			SWAP(xint, l, r);
		Node *x, *y, *z;
		sp(root, x, y, l-1);
		sp(y, y, z, r-l+1);
		y->rev();
		mg(y, y, z);
		mg(root, x, y);
	}

	sint max(xint l, xint r)
	{
		if (l > r)
			SWAP(xint, l, r);
		Node *x, *y, *z;
		sp(root, x, y, l-1);
		sp(y, y, z, r-l+1);
		sint m = y->max;
		mg(y, y, z);
		mg(root, x, y);

		return m;
	}
};


FHQ<int, int> t;


int main()
{
	_IO

	get(n, k)
	t.build(n);
	
	int op, l, r, v;
	while (k--)
	{
		sc(op)
		switch (op)
		{
			case 1:
				sc(l)sc(r)sc(v)
				t.inc(l, r, v);
				break;
			case 2:
				sc(l)sc(r)
				t.rev(l, r);
				break;
			case 3:
				sc(l)sc(r)
				PRT(t.max(l, r)), PC(10);
				break;
		}
	}

	return 0;
}

           

不得不说 FHQ Treap \text{FHQ Treap} FHQ Treap 实在是太强了。 Splay \text{Splay} Splay 能做的他都能做，线段树能做的他也能做，也能可持久化，还比他俩好写得多，速度也不算慢，还有笛卡尔式建树等等黑科技… 而这一切的基石仅是两个短小精悍、简洁灵巧的函数（ merge、split \text{merge、split} merge、split）。 FHQ \text{FHQ} FHQ 实在是惊为天人！