题解：CF2063F2 Counting Is Not Fun (Hard Version)

tooolazy · 2025-01-24 00:25:27 · 题解

来个诡异做法（idea by @liaoz123 thx

考虑先建括号树，怎么建之后说。

那么，对于括号树上的每一个节点，它对答案的贡献就是 H_m，其中 H 为卡特兰数，2m 为这个节点对应括号内部自由的字符数量。

具体的，由于限制形如括号配对，因此每一个括号的贡献是独立乘算的。对于一个包含了其它括号的括号，它可以自由决策的字符就是那些被自己包含且没有被其它子括号包含的字符。

只要能把优秀地维护括号树，那么计算 m 就是简单的，更新答案也是简单的。

现在的问题在于如何动态改树，这里就直接大力 DS 了吧（（（

具体的，由于匹配括号非包则无交，因此每次增加一对括号，其本质就是增加一个节点，并夺取原树某节点的一段连续儿子。

考虑直接 FHQ 维护儿子，直接切两刀就行了，所以非常好 O(n\lg n)。