自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:53:53，当前版本为作者最后更新于2024-01-08 08:46:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最喜欢的一集

首先思考一下查询一个串的最小操作次数怎么求。我们把括号树建出来，匹配的一对括号若不同则权值为 $1$ 否则是 $0$，发现翻转一个子串上的字符相当于翻转树上一条路径上的边权。那么问题就变成了最小操作次数使得全翻转成 $0$。这是一个经典问题，定义 $d_i$ 表示相邻 $1$ 边条数，答案为 $d$ 为奇数的点的个数除以二。

到这里还算阳间，让我们来看看原题还需要支持啥，需要支持区间 flip 跟区间查询“子区间”的答案的和。

首先我们知道区间 flip 是路径翻转了，不过需要注意的是原串不保证合法需要补成合法的串建括号树。区间内查询子区间的答案的和就很阴间了。首先我们发现一个区间不仅可以看成一条路径，还可以看成若干个子树的并。我们考虑怎么方便维护这些信息。

考虑直接上个静态 top tree 看看。

首先对于每个点的度数是奇数的个数拆成除根以外每个点的本身 $d$ 为奇数的个数和 $+$ 根连向每个儿子的 $1$ 边条数（设为 $d'$）是否为奇数。

考虑类似 rake 形式的合并。

维护 $f_i$ 表示 $i$ 子树内所有方案的答案和，$s_i$ 为 $i$ 子树内 $d$ 是奇数的个数。现在 $k$ 的儿子集合是 $S_k$，我们需要把这些儿子的信息合并起来。

建立 rake 树，每个虚点需要维护 $pre_{0/1},suf_{0/1}$ 表示每个前缀/后缀且根目前 $d'$ 为 $0/1$ 的答案的和/方案数，合并的时候考虑把 $pre$ 与 $suf$ 合并起来就行。

再考虑类似 compress 形式的合并，在 compress 树上我们发现可以记当前虚点代表的重链区间的两端是否为 $0/1$ 的所有方案的数量跟答案和，每次合并能把中间的这个点的贡献算出来。

信息的合并方式大概搓出来了，现在还有一个问题是路径 flip 还有查询。

路径 flip 是可以做的，只需要在 compress 树上加一个区间 flip 的操作还有在 rake 树上进行单点修改。

查询的话发现需要拆成这几部分：$x$ 的某个儿子区间的 $f$ 的和；$x \to lca$ 链的右半部分儿子 $f$ 的和；$lca$ 的某个儿子区间的 $f$ 的和；$lca \to y$ 链的左半部分的 $f$ 的和；$y$ 的某个儿子区间的 $f$ 的和。也就是说儿子的顺序也是影响答案的，所以需要在 compress 树上维护左右的答案的和。

那么大体整个题这样做就做完了。

代码：这是碰都不能碰的花题。