题解 P10012 [集训队互测 2023] 落日珊瑚

· · 题解

最喜欢的一集

首先思考一下查询一个串的最小操作次数怎么求。我们把括号树建出来，匹配的一对括号若不同则权值为 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 树上维护左右的答案的和。

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

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