题解：P11127 [ROIR 2024] 二叉树的遍历 (Day 2)

想了很久 polylog 做法无果，点开题解一看是全是根号做法，心脏骤停。

首先要对于点 $x,y$，大分讨 $y$ 比 $x$ 先遍历的情况。

这三种都可以预处理，因为第一、二种只关心 $x$ 的操作状态，而第三种不关心点的操作状态。

如果是单点修改，这两个也可以用树状数组简单做，但是这个是区间修改，在 dfs 序并不是一段连续的区间，很难做，只能考虑分块。

对于每个块维护数组 $f_i$ 表示块内的点对 dfs 序为 $i$ 的点（记为 $u$）的影响，即有多少点在 $u$ 前面，这样做是因为每个点的影响都是一个子树，子树点集在 dfs 序上是连续的。

注意到如果一个点是后序遍历，它不会对任何一个点产生影响，所以只考虑另外两种操作状态。

如果一个块内都是同一种操作状态，显然可以简单预处理维护，这要求修改区间完全包含它。

那么就考虑散块的情况，此时修改区间和它相交不包含，此时只能重构。

为什么重构复杂度是对的，每次修改至多需要重构两个散块。

此时需要构建一个新的 $f$ 数组，块内的 $\sqrt{n}$ 个点都将对其进行区间加法。

那么就是一共 $q\sqrt{n}$ 次修改，$q$ 次查询，用值域分块平衡一下复杂度即可（修改 $O(1)$，查询 $O(\sqrt{n})$），而散块共用同一个值域分块，整块可以 $O(1)$ 查，所以查询是 $O(\sqrt{n})$ 的。