CF1625E2 Cats on the Upgrade (hard version)

给出一个括号序列 \(s\),初始的时候没有 ., 每次操作有两种:

  • 1 l r:保证 \([l + 1, r - 1]\) 为空或者全是 . 并且 \(s_l\) = (,\(s_r\) = ),那么将 \(s_l, s_r\) 变成 .
  • 2 l r:定义合法的括号序列是满足括号匹配同时开头结尾均不是 .,求出 \([l, r]\) 中有多少个子串是合法的括号序列,保证 \([l, r]\) 是合法的括号序列。

对于简单版,保证没有修改操作


  数据结构 括号序列

  为什么会了 E1 但是没有想到 E2 啊啊啊啊。

  对于简单版,注意到可以根据建树,那么我们定义每个节点的权值 \(f_x = \sum_{y \in son_x} f_y + \binom{deg_x}{2} + 1\),然后因为给出的括号序列合法,然后每次询问就是框选了若干兄弟子树,于是答案为 \(\sum f_x + \binom{cnt}{2}\),\(cnt\) 代表兄弟子树的个数,然后就可以预处理 + 前缀和处理了。

  现在考虑修改,注意到这个 DP 是子树求和的形式 + 一个与 \(deg\) 有关的式子,于是我们可以考虑将每个节点的贡献设为 \(\binom{deg}{2} + 1\) 放到其在 \(s\) 中对应的左端点上。

  然后我们每次询问的时候,就是区间求和 + 我们目前框选的兄弟子树个数,其中前面一部分上一段已经讲完了,直接线段树 or 树状数组。

  现在考虑如何计算兄弟子树个数,我们注意到兄弟节点子树一定是这段区间中深度最小的点,于是我们可以再对于每个节点赋上一个深度的权值,这样我们也就是要求该权值最小的点的个数,这个也是线段树经典问题。

  至于修改,直接将贡献置为 \(0\),深度置为 \(\infty\) 即可。

  具体见代码

上一篇:如果git pull拉取分支出错,如何返回


下一篇:leetcode1220. 统计元音字母序列的数目(hard)