\texttt{FHQ-Treap yyds}

前言

这题搞得我吐了

不过第一次写模板题题解还是很开心的呀

感觉这道题题解质量都不高啊……

这里也会讲清楚此题题解并没有提及的一些重要问题。

看懂本篇题解，你需要了解 \texttt{FHQ-Treap} 的前置芝士。

题目连接：\text{Link}

题意简述

给定一个长度为 n 序列，第 i 项初始为 i。

支持区间翻转操作，即翻转区间 [l,r]。

输出 m 次翻转操作后的序列。

### 题目解析 这道题我是用的 $\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 的懒标记也就随之消失，因为已经它的儿子已经调换了。

而它的两个儿子调换之后，不光它们要调换，它们的后代也都要调换，所以它们也会承接父亲的懒标记，注意，这里的承接是指的取反，也跟上面讲述的同理，是为了节省翻多次的时间，这里不再赘述。

故到此，我们就实现了标记下传：

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}。没人发现这个可以点吗

所以，只有我们在分裂之前下传，才能传到真儿子中。当然，合并也是同理的。

这样一来，又有一个问题，我们在进行 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

时间复杂度：\mathcal{O}(n\log n)，树的深度约为 \log n。

空间复杂度：\mathcal{O}(n)。

求赞

\texttt{The End.by UF}