E2. Cats on the Upgrade (hard version)

题意

RBS定义为：它是一个只包含“(”，“）”以及“.”的字符串，若它能通过若干次删除“()”（一对连续的括号）或“.”，使得该字符串为空，则该字符串为RBS。

一个RBS是简单的，当且仅当它不为空，且第一个字符和最后一个字符都不是“.”。

初始状态下，给定一个长度为\(n\)的只包括“(”和“)”的字符串\(s\)。接下来，有\(q\)次操作或询问，一次操作或询问用t l r表示，\(t\)表示操作或询问的类型，\([l,r]\)表示操作或询问的区间。

\(t=1\)，使第\(l\)个字符和第\(r\)个字符变成“.”，输入保证操作时，第\(l\)个字符是“(”，第\(r\)个字符是“)”，且它们之间的字符都是“.”。

\(t=2\)，询问区间\([l,r]\)中，有多少个连续子串是简单RBS，输入保证操作时，区间\([l,r]\)代表的字符串是简单RBS。

分析

想到判断括号串合法的方法是通过栈：遇到“(”入栈，遇到“)”出栈，当遇到需要出栈，但栈却为空时，该括号串不合法。

结合题意中操作区间的保证，可以知道那些使得需要出栈，但栈却为空的“)”不会包含在操作的区间之内，故而可以将这些“)”替换成“.”，不会对结果产生影响。

经过上述替换后，题目所给字符串变成了RBS。

对于\(t=2\)询问来说，可以忽略所有字符串中的“.”

由于树的DFS是通过栈实现的，于是可以将入栈和出栈以树的形式记录下来，初始状态为一个节点，将其作为当前节点，遇到“(”就建立一个节点作为当前节点的儿子节点，并将当前节点移到儿子节点，遇到“)”就将当前节点移到当前节点的父亲节点。这样建立出来的树，以每个节点（除了根节点）为根的子树都代表了一个“(RBS)”，即一对“()”里面括了一个RBS串，特别地，根节点代表整个字符串。显然，叶子节点所代表的“(RBS)”中的“RBS”为空串。

询问区间\([l,r]\)代表的字符串一定是(RBS)(RBS)...(RBS)这样的形式，在树上就是某个节点的连续的一段儿子。假定每个括号里的RBS贡献之和为\(a\)，一共有\(k\)组(RBS)，那么合起来的贡献是\(\frac{k(k+1)}{2}+a\)。对于每个RBS，其所有儿子构成的整体也代表了一个(RBS)(RBS)...(RBS)，而叶子节点的“RBS”是空串，贡献为\(0\)，所以设每个节点的儿子个数是\(m\)，每个节点都维护它自己的\(\frac{m(m+1)}{2}\)作为权值，那么答案就是以某个节点的连续的一段儿子为根的子树森林里所有节点的权值之和再加上\(\frac{k(k+1)}{2}\)（显然\(k\)就是子树森林的根节点的数目）。

对于\(t=1\)修改来说，询问区间\([l,r]\)代表的字符串一定是(.........)这样的形式，在忽略了“.”的情况下，这个字符串的“()”里面一定是空串，所以，这是对叶子节点进行的操作。将左右两边变成“.”，就意味着这个叶子节点应该被删除，其父亲节点维护的权值需要更新。实际操作中叶子节点并没有被真的删除，只是将父亲节点维护的权值进行更新，让叶子节点不对其父亲产生贡献。

对于上述的操作，我们很容易想到用树状数组以DFS序的顺序维护节点权值的和，连续儿子为根的子树的权值和可以很容易通过DFS序进行区间表示。我们还需要询问这一段连续儿子的数量，以便计算\(\frac{k(k+1)}{2}\)，然而这是在有修改的情景下，并且实际的删除操作中叶子节点并没有被真的删除，所以相同区间下的连续儿子数可能会发生变化，故可以考虑对每个节点都开一个树状数组（儿子只会少不会多，所以每个节点只需要开初始有多少儿子那么大的数组即可），初始状态每个单点都是\(1\)，若某个儿子被删除，则将该单点设为\(0\)，某一段区间的连续儿子的数量可以通过区间查询查得。

我们可以在建树的过程中记录一些东西，从而实现\(O(1)\)快速找到区间\([l,r]\)中，DFS序的区间左端点和右端点，以及区间上一段连续儿子的左端点和右端点。进行一次修改或查询都只需要\(O(\log n)\)的时间，建树需要\(O(n \log n)\)的时间，整体时间复杂度为\(O((n+q)\log n)\)

代码

#include <cstdio>
#include <vector>
using namespace std;
typedef long long Lint;
const int maxn = 3e5 + 10;
struct Fenwick {
    vector<Lint> tr;
    int len;
    void build(int len) {
        tr.resize(len + 1);
        this->len = len;
    }
    void add(int pos, Lint val) {
        for (int i = pos; i <= len; i += i & -i) {
            tr[i] += val;
        }
    }
    Lint query(int pos) {
        Lint ans = 0;
        for (int i = pos; i > 0; i -= i & -i) {
            ans += tr[i];
        }
        return ans;
    }
}; // 树状数组
Fenwick tr[maxn], Tr; // tr为每个节点上开的树状数组，Tr为维护节点权值和的树状数组
char str[maxn];
int n, q;
int tot_node = 1, u = 1; // tot_node为当前节点数，u为当前节点
int fa[maxn], siz[maxn], idx[maxn]; // fa为父亲节点，siz为儿子个数，idx[x]为节点x是其父亲的第几个儿子（排行老几）
// [l,r]上，查询节点权值和使用[pos[l], pos[r]]区间进行查询
// [l,r]上，查询连续儿子数使用[idx[rt[l]], idx[rt[r]]]区间进行查询
int pos[maxn], rt[maxn]; 
int tot_st; // 栈深度
int main() {
    scanf("%d%d", &n, &q);
    scanf("%s", str);
    for (int i = 0; i < n; i++) {
        if (str[i] == '(') {
            ++tot_st;
            fa[++tot_node] = u;
            siz[u]++;
            idx[tot_node] = siz[u];
            pos[i + 1] = rt[i + 1] = tot_node;
            u = tot_node;
        } else if (tot_st) {
            --tot_st;
            pos[i + 1] = tot_node;
            rt[i + 1] = u;
            u = fa[u];
        }
    }
    Tr.build(n);
    for (int i = 1; i <= tot_node; i++) {
        Tr.add(i, (Lint)siz[i] * (siz[i] + 1) / 2);
        tr[i].build(siz[i]);
        for (int j = 1; j <= siz[i]; j++) {
            tr[i].add(j, 1);
        }
    }
    while (q--) {
        int t, l, r;
        scanf("%d%d%d", &t, &l, &r);
        if (t == 1) {
            int p = pos[l];
            Tr.add(fa[p], -siz[fa[p]]);
            --siz[fa[p]];
            tr[fa[p]].add(idx[p], -1);
        } else {
            int rt_l = rt[l], rt_r = rt[r];
            Lint ans = Tr.query(pos[r]) - Tr.query(pos[l] - 1);
            int p = fa[rt_l];
            int re = tr[p].query(idx[rt_r]) - tr[p].query(idx[rt_l] - 1);
            ans += (Lint)re * (re + 1) / 2;
            printf("%lld\n", ans);
        }
    }
    return 0;
}