题解 P3391 【【模板】文艺平衡树】

# $\texttt{FHQ-Treap yyds}$ ### 前言 这题搞得我吐了 不过第一次写模板题题解还是很开心的呀 感觉这道题题解质量都不高啊…… 这里也会讲清楚此题题解并没有提及的一些重要问题。 看懂本篇题解，你需要了解 $\texttt{FHQ-Treap}$ 的前置芝士。 题目连接：[$\text{Link}$](https://www.luogu.com.cn/problem/P3391) ### 题意简述 给定一个长度为 $n$ 序列，第 $i$ 项初始为 $i$。 支持区间翻转操作，即翻转区间 $[l,r]$。 输出 $m$ 次翻转操作后的序列。 $1\le n,m\le 10^5$。 ### 题目解析 这道题我是用的 $\texttt{FHQ-Treap}$，毕竟很好写。 既然都用 $\texttt{FHQ-Treap}$，那么大概率会有的一个想法就是：把 $[l,r]$ 这段区间在这棵平衡树上裂出来，然后再搞。 先别着急怎么裂，假设我们已经裂出来这棵树了，那么，这棵树里每个子节点的权值 $v$ 肯定有 $l\le v\le r$。 假设我们分裂出如下的一棵根节点为 $u$ 的一棵树（图中字母为编号）。  如果不考虑翻转的情况下，这棵树是要按照**中序遍历**来输出，即 $\texttt{c-a-d-u-b}$ 但如果翻转了呢？就把中序遍历给翻过来，也就是 $\texttt{b-u-d-a-c}$。 考虑我们到底肝了个什么事。 发现，其实就是把这棵树里，每一个节点的两个左右孩子调换后，得到的新树再进行中序遍历，所以上面的这棵树就变成了下面这个样子：  于是，我们一个初步的思路就是：分裂出对应的树后，从根开始，每一层的每一个节点都将两个儿子调换。 但是考虑我们这样的复杂度是多少，我们要进行分裂出来的树的节点的个数次调换，那么复杂度就是 $\mathcal{O}(r-l+1)$，最坏情况 $\mathcal{O}(n)$，跟朴素暴力一个德行，直接上天。 考虑优化，引入线段树那里的懒标记的思想。 还以这棵树为例，前提这棵树是分裂好的了：  现在想对这棵树进行翻转，我们可以先不翻转，而是记上要翻转的名义，那么在哪记？当然是这棵树的根节点也就是 $u$ 了。这里的标记是需要将原有的懒标记**取反**的，因为假设这同一个区间翻转了两次，就相当于啥都没干，取反两次翻转的名义也就没了。这样既省了时间复杂度，又省了代码复杂度。 现在问题又来了，我们光知道哪个树需要翻转，但是我们并没有真正地更改儿子，输出的时候怎么办。 这也是懒标记的精髓，用它的时候再更新。当我们要进行分裂、合并时，对于目前的节点 $u$，如果它有翻转的名义，也就是被标有懒标记了，那么，它的两个儿子其实就要调换了，而点 $u$ 的懒标记也就随之消失，因为已经它的儿子已经调换了。 而它的两个儿子调换之后，不光它们要调换，它们的后代也都要调换，所以它们也会承接父亲的懒标记，注意，这里的承接是指的取反，也跟上面讲述的同理，是为了节省翻多次的时间，这里不再赘述。 故到此，我们就实现了标记下传： ```cpp inline void push_down(int u) { tag[u]=false; Swap(ch[u][0],ch[u][1]); tag[ch[u][0]]^=1; tag[ch[u][1]]^=1; return; } ``` 之后还有一个问题：在分裂或合并时什么时候下传标记。 这个问题我想了半天，因为我太 $\texttt{naive}$ 了。因为我们在分裂的时候，对于一个节点 $u$，它的两个儿子就可能会改变，这样一来，假设我们在分裂之后来下传，可能会传到两个假儿子，就导致了 [$\texttt{\color{red}WA}$](https://www.luogu.com.cn/record/51863995)。~~没人发现这个可以点吗~~ 所以，只有我们在分裂之前下传，才能传到真儿子中。当然，合并也是同理的。 这样一来，又有一个问题，我们在进行 `push_down` 时，会调换两个儿子，那这样怎么能保证 $\texttt{treap}$ 的性质？ 其实，这道题，它跟权值是没有关系的，我们只关心每个子树内节点的顺序如何，我们维护的其实就是翻转后的中序遍历（个人理解）。 所以说我们回到本文开头笔者未解答的问题，怎么分裂出那棵需要翻转的子树？ 由于我很 $\texttt{naive}$，一直都是按照权值来分裂，然后一直爆蛋。因为当你下传标记的时候，这个树就已经满足不了**二叉搜索树的性质**了。 ~~那咋办，分裂不了啥都玩完了了，洗洗睡吧。~~ 既然我们不能按权值分，我们可以按照子树的大小来分！也就是 $\texttt{FHQ-Treap}$ 另一种经典分裂途径。 这样分裂，简单来说，就是分出权值的效果，但又不需要权值。 然后假设我们有如下的一棵树。  圈内代表节点编号，红字代表节点的值。 它显然不满足 $\texttt{BST}$ 的性质，因为我们维护的是中序遍历。 那么目前，此序列即为 $\texttt{2-3-5-1-4}$ 这是按照对此树中序遍历得来的。 有一个很显然的性质：对于目前序列一个连续的区间，在这棵树中所对应的节点也是相连的。 那么也很显然，我们只要分裂两次就能分裂出我们先要的区间。 那么分裂就显而易见了，对于翻转 $[l,r]$，我们先把 $[1,l-1]$ 这个区间分裂，也就是大小为 $l-1$ 的子树分裂，然后对于这个 $[l,n]$ 的这个树，我们分裂出大小 $r-l+1$ 的一棵树。这个只要你知道啥是按大小分裂都能想清楚吧。 之后就是输出了，当然就是按照中序遍历输出，但还有一个问题，有些节点可能标记没下传下去，遍历的时候也要下传。 呼，讲完了，此生最长的一片题解了 [$code$](https://paste.ubuntu.com/p/bwpzbrf6HG/) 时间复杂度：$\mathcal{O}(n\log n)$，树的深度约为 $\log n$。 空间复杂度：$\mathcal{O}(n)$。 求赞 $$\texttt{The End.by UF}$$