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

Lucyna_Kushinada · 2025-10-06 18:37:55 · 题解

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

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

• 存在一个 x,y 的公共祖先 z，y 在 z 左子树，x 在 z 的右子树。

这三种都可以预处理，因为第一、二种只关心 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}) 的。