题意简述

给定一个长度为 $n$ 的初始只包含 ( 和 ) 的字符串 $s$。需要处理 $q$ 个操作，操作分两类：

1. 删除操作：给定 $l, r$，保证 $s_l = \text{`(`}$，$s_r = \text{`)`}$，且 $s_{l+1}\dots s_{r-1}$ 全是 '.'。将 $s_l$ 和 $s_r$ 也改为 '.'。
2. 查询操作：给定 $l, r$，保证 $s[l..r]$ 是一个简单 RBS（即它是一个非空的正则括号序列，且不以 '.' 开头或结尾）。询问 $s[l..r]$ 中包含多少个简单 RBS 子串（即有多少对 $(i,j)$ 满足 $l\le i<j\le r$ 且 $s[i..j]$ 是简单 RBS）。

问题转化

首先，不考虑删除操作时，字符串由 ( 和 ) 构成。经典的括号匹配可以建立一棵树：

• 每个匹配的括号对 $(l,r)$ 对应树中的一个节点，其区间为 $[l,r]$。
• 若括号对 $u$ 直接包含括号对 $v$（即 $l_u < l_v < r_v < r_u$，且中间没有其他括号对跨越），则 $u$ 是 $v$ 的父亲。
• 所有不被任何括号对包含的顶层括号对，均为虚拟根（编号 $0$）的子节点。

例如，字符串 ()(()) 的树结构如下：

虚拟根
 ├─ 节点1: [1,2]
 └─ 节点2: [3,6]
     └─ 节点3: [4,5]

每个节点 $u$ 对应一个简单 RBS（它的区间本身就是简单 RBS）。此外，对于一个节点 $u$，若它有 $k$ 个直接子节点，则这些子节点按照在字符串中出现的顺序排列。任意连续的一段子节点（长度可以为 $1$）的并集也构成一个简单 RBS。这些简单 RBS 恰好涵盖了 $u$ 的区间内所有不以 $u$ 的左右括号为端点的简单 RBS。而 $u$ 自身作为一个简单 RBS，会被计入其父节点的“连续子节点段”中。

因此，定义每个节点 $u$ 的贡献为：

$$f(u)=\frac{k_u(k_u+1)}{2},$$

其中 $k_u$ 是节点 $u$ 的直接子节点个数（注意虚拟根的 $k_0$ 为顶层括号对数）。那么整个字符串中所有简单 RBS 子串的总数恰好等于所有节点（含虚拟根）的 $f$ 之和。这是因为：

• 任意一个简单 RBS 子串要么是某个节点本身（对应其父节点下的长度为 $1$ 的子段），要么是某个节点下的一段长度 $\ge 2$ 的连续子节点段，这些贡献都被 $f(u)$ 统计到。

对于查询操作，给定一个简单 RBS 子串 $s[l..r]$，它对应树中的某个节点 $u$ 的一段连续子节点（可能只包含一个子节点，也可能包含多个）。具体定位方法：

• 找到位置 $l$ 所在的最内层节点 $x$（即包含 $l$ 的节点中区间最小的），由于 $s[l]$ 是 '('，所以 $l$ 一定是某个节点的左端点。
• 类似地找到位置 $r$ 所在的最内层节点 $y$，$r$ 是 $y$ 的右端点。
• 因为 $s[l..r]$ 是简单 RBS，$x$ 和 $y$ 必定是同一个父节点 $p$ 下的连续兄弟节点，设它们为 $v_{L}, v_{L+1}, \dots, v_{R}$。

此时，$s[l..r]$ 内包含的所有简单 RBS 子串分为三类：

1. 完全位于某个 $v_i$ 内部（但不包括 $v_i$ 自身）的子串，数量为 $S(v_i)-f(v_i)$，其中 $S(u)=\sum_{w\in \text{subtree}(u)} f(w)$ 是以 $u$ 为根的子树和。
2. $v_i$ 自身作为一个简单 RBS，共 $R-L+1$ 个。
3. 由连续多个 $v_i$ 构成的子段（长度 $\ge 2$），共 $\binom{R-L+1}{2}$ 个。

因此答案为：

$$\text{ans} = \sum_{i=L}^{R} \bigl(S(v_i)-f(v_i)\bigr) + (R-L+1) + \binom{R-L+1}{2}. $$

整理得：

$$\text{ans} = \sum_{i=L}^{R} S(v_i) - \sum_{i=L}^{R} f(v_i) + \frac{k(k+1)}{2}, $$

其中 $k=R-L+1$。

这样，如果我们能快速求出任意节点的子树和 $S(u)$，以及单个节点的 $f(u)$，就可以回答查询。

删除操作的影响

操作 $1$ 删除一个叶子节点（因为题目保证 $l$ 和 $r$ 之间全是 .，所以该括号对内部的所有括号都已被删除，即它没有子节点）。设被删除的节点为 $u$，其父节点为 $p$。

• 删除 $u$ 后，$p$ 的直接子节点数 $k_p$ 减少 $1$，因此 $f(p)$ 从 $\frac{k_p(k_p+1)}{2}$ 变为 $\frac{(k_p-1)k_p}{2}$，减少了 $k_p$。
• 同时，$p$ 的祖先节点们的 $f$ 值不变（因为它们统计的是自己的子节点数，$p$ 的删除不影响祖先的直接子节点数），但是它们的子树和 $S$ 会因为 $p$ 的 $f$ 变化而改变。具体地，从 $p$ 到根路径上的每个节点 $x$，其 $S(x)$ 都会减少 $k_p$（因为 $p$ 的 $f$ 减少了 $k_p$，而 $S(x)$ 包含 $p$ 的贡献）。

因此，一次删除操作会使根到 $p$ 路径上所有节点的子树和 $S$ 都减少 $k_p$。注意，$k_p$ 是删除前 $p$ 的子节点数，因为删除后 $p$ 的子节点数变为 $k_p-1$。

两种解法

解法一：根号分治

因为每次删除只影响一条到根的路径，我们可以用根号重构的方法平衡修改和查询。

设块大小 $B = \lceil \sqrt{n} \rceil$。每处理 $B$ 次操作后，我们完全重建整棵树（根据当前的字符串重新建树，并计算所有 $f(u)$ 和 $S(u)$）。在两次重建之间，我们维护一个被删除的叶子节点列表（这些节点在最近一次重建之后被删除了）。对于一次查询 $2$，其答案由两部分组成：

• 基于最近一次重建的树计算出的答案（即假设没有任何删除操作发生）。
• 对于列表中的每个被删除节点，如果它位于查询区间内，则需要减去它对答案造成的损失。

具体地，重建后我们得到每个节点的 $f(u)$ 和 $S(u)$。对于查询 $[l,r]$，我们先通过括号匹配找到对应的连续兄弟节点段 $[L,R]$，然后根据公式计算出一个初始答案 $ans_0$。接着，遍历删除列表中的每个节点 $u$（它一定是一个叶子节点）：

• 若 $u$ 的区间 $[l_u, r_u]$ 完全包含在查询区间 $[l,r]$ 内，则删除 $u$ 会使得答案减少 $k_{p}$，其中 $p$ 是 $u$ 的父亲（在重建时的树中）。注意，如果 $p$ 本身也被删除了，则 $u$ 的祖先路径可能已经变化，但因为我们每次重建后只处理在本次重建之后被删除的节点，且删除顺序中父亲一定比孩子先删除（因为删除叶子节点时其子节点已全部是 .，故孩子一定先被删），所以父亲一定还在树中。这样我们只需累加这些损失。
• 若 $u$ 的区间不完全在 $[l,r]$ 内，则忽略。

遍历所有删除节点后，用 $ans_0$ 减去总损失，即为最终答案。

每次查询的复杂度为 $O(B)$（遍历删除列表），每 $B$ 次操作后重建的复杂度为 $O(n)$（建树和 DP）。总复杂度 $O((n+q)\sqrt{n})$，可以通过 $3\times 10^5$ 的数据。

解法二：树状数组 + 欧拉序

我们可以用更优秀的数据结构做到 $O((n+q)\log n)$。

注意到删除操作只影响从被删节点父亲到根的路径，而查询操作需要求某个连续兄弟段内所有节点的子树和 $S(v_i)$ 以及 $f(v_i)$。我们可以用欧拉序将子树转化为区间，然后用树状数组维护每个节点的 $S$ 值（即子树和）。但 $S$ 会随着删除而动态变化，且每次变化是对一条路径上的所有节点进行区间加（因为 $S(x)$ 减少 $k_p$，而 $x$ 的欧拉序区间是连续的，但路径上的节点并不对应欧拉序上的连续区间，所以需要树链剖分）。

实际上，更好的方法是：我们不直接维护 $S(u)$，而是维护每个节点的 $f(u)$，并用树状数组支持子树求和。因为 $S(u)$ 就是 $u$ 子树中所有 $f$ 之和，而 $f$ 只会因为其父节点的子节点数变化而改变。当删除一个叶子节点 $u$（其父亲为 $p$）时，$f(p)$ 减少 $k_p$（原来的子节点数）。这相当于将 $p$ 的 $f$ 值减去 $k_p$，同时由于 $f(p)$ 的改变，所有包含 $p$ 的祖先的 $S$ 都会变化，但这些祖先的 $S$ 并不需要显式存储，我们只需在查询时动态计算子树和即可。查询 $S(v)$ 时，我们可以通过树状数组查询 $v$ 子树内所有 $f$ 的和，因此 $S(v)$ 是可以在线计算的。

具体算法：

1. 初始建立树，计算每个节点 $u$ 的 $f(u)=\frac{k_u(k_u+1)}{2}$（其中 $k_u$ 为直接子节点数）。将 $f(u)$ 放入树状数组（位置为 $u$ 的欧拉序区间）。
2. 对于删除操作 $1$，找到被删除的叶子节点 $u$ 及其父亲 $p$。令 $k_p$ 为 $p$ 当前的子节点数（即删除前）。将 $f(p)$ 减少 $k_p$（即树状数组中 $p$ 位置的值加上 $-k_p$）。然后将 $p$ 的子节点数减 $1$（以便下次删除时用）。
3. 对于查询操作 $2$，先通过括号匹配找到对应的连续兄弟节点段 $[L,R]$（即节点序列）。对于每个 $v_i$，用树状数组查询其子树和得到 $S(v_i)$，同时我们知道 $f(v_i)$（可直接访问）。然后按照公式计算答案：$$\text{ans} = \sum_{i=L}^{R} S(v_i) - \sum_{i=L}^{R} f(v_i) + \frac{k(k+1)}{2}, $$其中 $k=R-L+1$。

这样，每次修改和查询都是 $O(\log n)$ 的（求子树和使用树状数组 + 欧拉序，需要预处理每个节点的 DFS 序区间）。总复杂度 $O((n+q)\log n)$。

实现细节

建树与括号匹配

使用栈：遍历字符串，遇到 '(' 时创建一个新节点，节点编号递增，将其入栈；遇到 ')' 时弹出栈顶节点 $u$，此时 $u$ 的右端点即为当前位置。若栈非空，则栈顶节点 $v$ 是 $u$ 的父亲，将 $u$ 加入 $v$ 的子节点列表。同时，记录每个位置所属的节点（比如用数组 node_of_pos[i] 表示位置 $i$ 属于哪个节点，对于 '(' 和 ')' 都是同一个节点）。

注意，初始字符串只有 '(' 和 ')'，没有 .。删除操作后会出现 .，但在树中我们只关心未被删除的括号对。重建时，我们需要根据当前字符串（含有 .）重新建树，仅考虑未被删除的括号对。由于删除操作保证每次删除的节点都是叶子，且删除后该位置的字符变为 .，因此重建时只需扫描字符串，忽略 .，只对 '(' 和 ')' 进行匹配即可。

处理查询区间对应的节点段

给定 $l, r$ 且 $s[l..r]$ 是简单 RBS：

• 找到 $l$ 所属的节点 $x$（即 $l$ 是 $x$ 的左端点）。
• 找到 $r$ 所属的节点 $y$（即 $r$ 是 $y$ 的右端点）。
• 如果 $x = y$，则查询区间就是单个节点 $x$，此时 $k=1$，连续兄弟节点段只包含 $x$ 本身。
• 否则，$x$ 和 $y$ 必定是同一个父节点 $p$ 下的连续兄弟节点。我们可以利用父节点的子节点列表，找到 $x$ 和 $y$ 在列表中的下标，从而得到 $[L,R]$。

为了快速定位，可以预处理每个节点在其父节点子节点列表中的索引（即 order_in_parent）。

欧拉序与子树求和

对树（含虚拟根）进行 DFS，记录每个节点的进入时间 tin[u] 和离开时间 tout[u]，则子树 $u$ 对应区间 [tin[u], tout[u]]。用树状数组维护每个节点的 $f(u)$ 值，在修改时单点更新，查询子树和时区间查询。

初始化

初始时所有节点均存在，计算每个节点的子节点数 $k_u$ 和 $f(u)$，并初始化树状数组。

复杂度分析

• 解法一：$O((n+q)\sqrt{n})$，空间 $O(n+q)$。
• 解法二：$O((n+q)\log n)$，空间 $O(n+q)$。

两种解法均可通过本题的困难版本。

示例模拟

以题目样例为例，初始字符串 )(()())()，建树后节点信息如下（虚拟根 $0$）：

• 节点 $1$：区间 $[2,3]$，子节点无 → $f=0$
• 节点 $2$：区间 $[4,7]$，子节点 $[5,6]$ → $f=1$（因为 $k=1$，$1\cdot2/2=1$）
• 节点 $3$：区间 $[5,6]$，子节点无 → $f=0$
• 节点 $4$：区间 $[8,9]$，子节点无 → $f=0$ 顶层括号有 $[2,3]$, $[4,7]$, $[8,9]$，故虚拟根 $k=3$，$f=3\cdot4/2=6$。

查询 $2\ 3\ 6$：对应节点 $2$ 的区间，子节点段为 $[5,6]$ 即节点 $3$ 自身。计算：$S(3)=f(3)=0$，$k=1$，答案 $=0-0+1=1$？但样例输出 $3$，说明我理解有偏差。重新审视样例：第一次查询 $2\ 3\ 6$，字符串下标从1开始：)(()())()，位置3是 '('，位置6是 ')'，子串 (()()) 是一个简单RBS，它对应节点 $2$ 的整个区间 $[4,7]$？注意位置3是第2个字符？实际上字符串索引：1:')',2:'(',3:'(',4:')',5:'(',6:')',7:')',8:'(',9:')'。所以 $l=3$ 是 '('，$r=6$ 是 ')'，子串 $s[3..6] = "()()"$？不对， $s[3]='(', s[4]=')', s[5]='(', s[6]=')'$，所以是 ()()，这是一个简单RBS，它对应两个兄弟节点（节点1? 节点1是$[2,3]$? 有点乱）。可见之前构建树需要根据实际匹配。正确的匹配应该是：括号对: (2,3), (4,7), (5,6), (8,9)。其中 (5,6) 是 (4,7) 的子节点。所以 $s[3..6]$ 实际上是 $[3,6]$，它包含两个括号对: [3,4]? 位置3是 '(' 但匹配的 ')' 在位置4？位置4是 ')'，但位置2是 '(' 匹配位置3? 实际上标准括号匹配: 位置2 '(' 匹配位置3 ')'，所以节点 [2,3]。位置4 '(' 匹配位置7 ')'，节点 [4,7]。位置5 '(' 匹配位置6 ')'，节点 [5,6] 是 [4,7] 的子节点。位置8 '(' 匹配位置9 ')'，节点 [8,9]。那么 $s[3..6]$ 从位置3到6：位置3是 ')'，位置4是 '('，位置5是 '('，位置6是 ')'，得到字符串 )(()？这也不是简单RBS。所以我的索引可能有误。根据样例解释，第一个查询结果是3，子串有 $s[3..6], s[3..4], s[5..6]$。其中 $s[3..4]$ 是 ()，$s[5..6]$ 是 ()，$s[3..6]$ 是 ()()。所以 $s[3..6]$ 的确是 ()()，那么位置3应该是 '('，位置4是 ')'，位置5是 '('，位置6是 ')'。所以原字符串 )(()())() 应该解释为：1:')',2:'(',3:'(',4:')',5:'(',6:')',7:')',8:'(',9:')'？这样位置3是 '('，位置4是 ')'，位置5是 '('，位置6是 ')'，得到 ()()。但位置2是 '('，位置3是 '('，所以节点 [2,3] 是 () 吗？位置2 '(' 匹配位置3 ')'，所以节点 [2,3] 正确。位置4 '(' 匹配位置7 ')'，节点 [4,7] 包含位置5,6 作为子节点。所以 $s[3..6]$ 实际上是从位置3到6，包含了节点 [2,3] 的右括号和节点 [4,7] 的左括号部分，不是完整的节点。因此，$s[3..6]$ 对应的兄弟节点段应该是虚拟根下的节点？虚拟根下的子节点有 [2,3], [4,7], [8,9]。其中 [2,3] 的右端是3，[4,7] 的左端是4，所以 $[3,6]$ 不是一个完整的连续子节点段（因为缺少 [2,3] 的左括号和 [4,7] 的右括号）。但实际上它是简单RBS ()()，它由两个独立的括号对 [3,4] 和 [5,6] 组成。但 [3,4] 并不是一个节点，因为括号对 [2,3] 占据了2和3，3已经被用过了。所以这暴露出一个问题：原始括号匹配中，每个位置只能属于一个节点，但这里的 () 出现在位置3-4，而位置3已经作为节点 [2,3] 的右括号了，矛盾。因此，我最初的匹配有误。正确的匹配应该是：字符串 )(()())()，让我们手动匹配： 位置1: ')' 位置2: '(' 位置3: '(' 位置4: ')' 位置5: '(' 位置6: ')' 位置7: ')' 位置8: '(' 位置9: ')' 扫描： i=1: ')', 无法匹配。 i=2: '(' push 2 i=3: '(' push 3 i=4: ')' pop 3, 节点 [3,4] i=5: '(' push 5 i=6: ')' pop 5, 节点 [5,6] i=7: ')' pop 2, 节点 [2,7] (因为2和7匹配) i=8: '(' push 8 i=9: ')' pop 8, 节点 [8,9] 所以正确的节点是：A=[3,4], B=[5,6], C=[2,7], D=[8,9]。其中 C 的子节点是 A 和 B。顶层节点是 C 和 D（以及位置1的 ')' 无法匹配，忽略？实际上位置1的 ')' 没有匹配，所以整个字符串不是合法的括号序列，但题目不要求全局合法，只要求查询的区间是简单RBS。那么我们的树应该只包含匹配的括号对，位置1的 ')' 视为无意义字符（在树中不考虑）。因此虚拟根的子节点为 C 和 D。现在看查询 $2\ 3\ 6$：$l=3$ 是节点 A 的左括号，$r=6$ 是节点 B 的右括号，它们属于同一个父节点 C 下的连续兄弟节点 [A, B]。所以 $k=2$，$S(A)=f(A)=0$，$S(B)=f(B)=0$，$f(A)=0,f(B)=0$，答案 $=0+0-0-0+2\cdot3/2=3$，符合输出。因此我们的模型是正确的。

通过这个例子，验证了公式：

$$\text{ans} = \sum_{i=L}^R S(v_i) - \sum_{i=L}^R f(v_i) + \frac{k(k+1)}{2}. $$

其中 $S(v_i)$ 是 $v_i$ 子树内所有节点的 $f$ 之和。

代码框架

// 伪代码，展示核心数据结构
int n, q;
string s;
vector<int> adj[N]; // 树
int parent[N], child_cnt[N];
int tin[N], tout[N], dfn;
int f[N]; // f[u] = child_cnt[u]*(child_cnt[u]+1)/2
LL bit[N]; // 树状数组

void dfs(int u) {
    tin[u] = ++dfn;
    for (int v : adj[u]) dfs(v);
    tout[u] = dfn;
}

void build() {
    // 根据当前字符串重建树
    stack<int> st;
    // 建立虚拟根0
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '(') {
            int u = ++tot;
            pos_node[i] = u;
            if (!st.empty()) {
                int p = st.top();
                adj[p].push_back(u);
                parent[u] = p;
            } else {
                adj[0].push_back(u);
                parent[u] = 0;
            }
            st.push(u);
        } else if (s[i] == ')') {
            int u = st.top(); st.pop();
            pos_node[i] = u;
        }
    }
    // 计算子节点数
    for (int u = 0; u <= tot; ++u) {
        child_cnt[u] = adj[u].size();
        f[u] = 1LL * child_cnt[u] * (child_cnt[u] + 1) / 2;
    }
    // DFS 序
    dfn = 0;
    dfs(0);
    // 初始化树状数组
    for (int u = 0; u <= tot; ++u) {
        bit.add(tin[u], f[u]);
    }
}

void delete_node(int u) {
    int p = parent[u];
    int k = child_cnt[p]; // 删除前的子节点数
    // 更新 f[p]
    LL delta = -k; // f[p] 减少了 k
    f[p] += delta;
    bit.add(tin[p], delta);
    child_cnt[p]--;
    // 删除节点 u（不再使用）
}

LL query_subtree_sum(int u) {
    return bit.query(tout[u]) - bit.query(tin[u]-1);
}

LL query_range(int l, int r) {
    // 找到节点段 [L,R]
    int x = pos_node[l], y = pos_node[r];
    if (x == y) {
        // 单个节点
        LL Sx = query_subtree_sum(x);
        return Sx - f[x] + 1; // k=1
    } else {
        // 找到父节点 p，以及 x 和 y 在子节点列表中的下标
        int p = parent[x]; // 与 parent[y] 相同
        int idxL = order[x], idxR = order[y];
        int k = idxR - idxL + 1;
        LL sumS = 0, sumF = 0;
        for (int i = idxL; i <= idxR; ++i) {
            int v = adj[p][i];
            sumS += query_subtree_sum(v);
            sumF += f[v];
        }
        return sumS - sumF + 1LL * k * (k + 1) / 2;
    }
}

实际实现时，需要维护每个节点在其父节点子节点列表中的位置（order），以及快速根据位置找到节点（例如用数组 node_at_order[p][i]）。因为树会重建，所以每次重建后重新计算这些信息。

对于根号分治，还需要维护一个删除列表，并在每次查询时遍历列表计算损失。

最终，按照上述两种方法之一即可通过本题。