升级中的猫 (Cats on the Upgrade, CF1625E)

我们称一个字符串\(s\)叫做\(RBS\), 如果它满足如下要求:

\((1)\) \(s\)只包含"\((\)", "\()\)", "\(.\)"这\(3\)种字符.

\((2)\) \(s\)可以通过逐步删去一个"\(.\)"或者一对括号"\(()\)"来变成一个空串.

比如, 字符串"\((()(.))\)"就是一个\(RBS\). 因为它可以通过如下方式变成一个空串:

"\((()(\underline{.}))\)"\(\rightarrow\)"\((()\underline{()})\)"\(\rightarrow\)"\((\underline{()})\)"\(\rightarrow\)"\(\underline{()}\)"\(\rightarrow\)"".

如果一个\(RBS\)非空, 并且首字符和尾字符都不是"\(.\)", 那么称它是简单\(RBS\).

给你一个长度为\(n(2\leq n\leq 3\times 10^5)\), 由"\((\)"和"\()\)"组成的字符串\(s\)(下标从\(1\)开始). 接下来有\(q(1\leq q \leq 3\times 10^5)\)个询问. 询问有两种类型:

\(1\ l\ r\): 给你两个下标\(l, r(1\leq l<r\leq n)\), 保证\(s_l\)为"\((\)", \(s_r\)为"\()\)", 且\(s_l\)和\(s_r\)之间的字符全部为"\(.\)". 然后把\(s_l\)和\(s_r\)都改为"\(.\)".

\(2\ l\ r\): 给你两个下标\(l, r(1\leq l<r\leq n)\), 保证子串\(s[l,r]=s_ls_{l+1}...s_r\)是简单\(RBS\), 输出满足\(l\leq i<j\leq r, s[i,j]\)是简单\(RBS\)的有序整数对\((i,j)\)的个数.

[分析]

首先, 利用栈可以得到初始串\(s\)的每个括号是否有对应匹配的括号, 且如果能匹配则对应的括号唯一. 忽略掉没有匹配的括号后, 我们把每个括号对视为一个树节点, 并定义一个虚拟节点\(0\)(相当于在字符串\(s\)外再套一个括号). 于是节点\(u\)是节点\(v\)的父亲, 当且仅当括号对\(u\)包含括号对\(v\), 且不存在括号对\(w\), 使得\(u\)包含\(w\), \(w\)包含\(v\)(由于每个括号对都可视作被括号对\(0\)包含, 所以\(s\)中所有点都有父节点). 利用栈即可完成建树, 这样得到一棵根节点为\(0\)的有根树.

我们考虑用树来刻画两种询问, 则询问\(1\)相当于删除\(1\)个叶子节点. 考虑询问\(2\). 由于询问\(2\)中的子串\(s[l,r]\)是简单\(RBS\), 因此询问\(2\)中\(l\)对应的括号对\(u\)和\(r\)对应的括号对\(v\)一定有公共的父亲节点(记为\(f\)). 记\(ord_u\)表示点\(u\)是点\(f\)的第\(ord_u\)个子节点(按照括号的出现顺序), 则\(ord_u\leq ord_v\). 考虑点\(f\)以及以\(f\)的第\(ord_u\), \(ord_u+1\), ..., \(ord_v\)个子节点为根节点的子树, 这些所有点构成以\(f\)为根节点的子树(记为树\(F\)). 则答案即为对于子树的每一个节点, 以该节点为父节点, 选取它按出现顺序的连续一段子节点的方案数之和.

记\(siz_u\)表示节点\(u\)的子节点个数. 当\(u\neq f\)时, 树\(F\)中\(u\)的子节点个数就是\(siz_u\). 因此选取它按出现顺序的连续一段子节点的方案数为\(\frac{siz_u(siz_u+1)}{2}\). 当\(u=f\)时, 树\(F\)中\(f\)的子节点个数为\(ord_v-ord_u+1\). 方案数为\(\frac{(ord_v-ord_u+2)(ord_v-ord_u+1)}{2}\). 将树\(F\)中所有节点的答案相加即为询问的答案.

当删除一个叶子节点\(u\)时, \(u\)的父节点\(f\)的子节点个数减\(1\). 且\(f\)的子节点中所有出现顺序在\(u\)之后的节点\(ord\)也要减\(1\). 后者的修改可以用树状数组来解决: 对每个节点\(f\)开一个大小为\(siz_f\)的树状数组\(o_f\), 记\(ord'_u\)为当前\(u\)在其父节点的所有子节点中的出现顺序(一开始\(ord'_u=ord_u\)), 则\(o_{f,ord_u}=1\)表示\(u\)未被删除, \(o_{f,ord_u}=0\)表示\(u\)被删除. 于是用树状数组维护\(ord'_u=\sum\limits_{i=1}^{ord_u}o_i\)即可. 前者修改也可以用树状数组解决: 考虑以\(0\)为根节点的有根树的\(dfs\)序, 则以\(f\)的第\(ord_u\), \(ord_u+1\), ..., \(ord_v\)个子节点为根节点的子树构成的森林在\(dfs\)序上是连续的. 设\(lef_u,rig_u\)为节点\(u\)的\(dfs\)序最小值和最大值. 我们构造一个树状数组\(C\), 对每个节点\(u\)令\(C_{lef_u}\)的初始值为\(\frac{siz_u(siz_u+1)}{2}\), \(C\)中其它元素初始值为\(0\). 于是每次只需要单点修改\(siz_f\)和\(C_{lef_f}\)的值即可. 设第\(2\)种询问对应的左右节点为\(u,v\), 则答案为\(\frac{(ord'_v-ord'_u+2)(ord'_v-ord'_u+1)}{2}+\sum\limits_{i=lef_u}^{rig_v}C_i\). 后者求和用树状数组即可快速求出.

总时间复杂度为\(O((q+n)logn)\).