E2. Cats on the Upgrade (hard version)

meaning of the title

RBS is defined as: it only contains "(", ")" and "." If it can delete "()" (a pair of consecutive parentheses) or "." several times, If the string is empty, the string is RBS.

An RBS is simple if and only if it is not empty and the first and last characters are not ".".

In the initial state, a string \ (s \) with a length of \ (n \) including only "(" and ")" is given. Next, there are \ (q \) operations or queries. One operation or query is represented by t l r, \ (t \) represents the type of operation or query, and \ ([l,r] \) represents the interval of operation or query.

\(t=1 \), so that the characters \ (l \) and \ (r \) become ".", When entering the guarantee operation, the \ (l \) character is "(", the \ (r \) character is ")", and the characters between them are ".".

\(t=2 \), ask how many consecutive substrings in the interval \ ([l,r] \) are simple RBS. When entering the guarantee operation, the string represented by the interval \ ([l,r] \) is simple RBS.

analysis

Think of the method to judge the legitimacy of the bracket string through the stack: encounter "(" into the stack, encounter ")" out of the stack. When it needs to be out of the stack, but the stack is empty, the bracket string is illegal.

In combination with the guarantee of the operation interval in the meaning of the question, we can know that the ")" that makes it necessary to get out of the stack but the stack is empty will not be included in the operation interval, so these ")" can be replaced with ".", Will not affect the results.

After the above replacement, the string given by the title becomes RBS.

For \ (t=2 \) queries, "." in all strings can be ignored

Since the DFS of the tree is realized through the stack, the input and output of the stack can be recorded in the form of a tree. The initial state is a node and takes it as the current node. When it encounters "(", it establishes a node as the child node of the current node and moves the current node to the child node. When it encounters ")", it moves the current node to the parent node of the current node. The subtree with each node (except the root node) as the root of the tree established in this way represents a "(RBS)", that is, a pair of "()" contains an RBS string. In particular, the root node represents the whole string. Obviously, the "RBS" in the "(RBS)" represented by the leaf node is an empty string.

The string represented by the query interval \ ([l,r] \) must be (RBS) (RBS) (RBS) in this form, it is a continuous section of the son of a node in the tree. Assuming that the sum of RBS contributions in each bracket is \ (a \) and there are \ (k \) groups (RBS), the combined contribution is \ (\ frac{k(k+1)}{2}+a \). For each RBS, the whole of all its sons also represents one (RBS) (RBS) (RBS), and the "RBS" of the leaf node is an empty string with a contribution of \ (0 \), so let the number of sons of each node be \ (m \), and each node maintains its own \ (\ frac{m(m+1)}{2} \) as the weight, Then the answer is the sum of the weights of all nodes in the subtree forest with a continuous section of sons of a node as the root, plus \ (\ frac{k(k+1)}{2} \) (obviously \ (k \) is the number of root nodes of the subtree forest).

For the modification of \ (t=1 \), the string represented by the query interval \ ([l,r] \) must be (...) This form ignores "." In this case, the "()" of this string must be an empty string, so this is an operation on the leaf node. Turn the left and right sides into ".", This means that the leaf node should be deleted and the weight maintained by its parent node needs to be updated. In practice, the leaf node is not really deleted, but the weight maintained by the parent node is updated so that the leaf node does not contribute to its father.

For the above operations, it is easy to think of using a tree array to maintain the sum of node weights in DFS order. The sum of weights of subtrees with continuous sons as roots can be easily expressed in intervals through DFS order. We also need to ask the number of consecutive sons in this section to calculate \ (\ frac{k(k+1)}{2} \), but this is in the case of modification, and the leaf node is not really deleted in the actual deletion operation, so the number of consecutive sons in the same interval may change, Therefore, it can be considered to open a tree array for each node (the number of sons will be small or not, so each node only needs to open an array as large as the initial number of sons). Each single point in the initial state is \ (1 \). If a son is deleted, set the single point to \ (0 \), and the number of consecutive sons in a certain interval can be found through interval query.

We can record some things in the process of building a tree, so as to realize \ (O(1) \) to quickly find the left and right endpoints of the interval of DFS order in the interval \ ([l,r] \), as well as the left and right endpoints of a continuous son on the interval. It takes only \ (O(\log n) \) to make a modification or query, and \ (O(n \log n) \) to build a tree. The overall time complexity is \ (O((n+q)\log n) \)

code

#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;
    }
}; // Tree array
Fenwick tr[maxn], Tr; // TR is the tree array opened on each node, and TR is the tree array maintaining the sum of node weights
char str[maxn];
int n, q;
int tot_node = 1, u = 1; // tot_node is the current number of nodes, and u is the current node
int fa[maxn], siz[maxn], idx[maxn]; // fa is the father node, siz is the number of sons, idx[x] is the node, and X is the father's oldest son
// On [l,r], query node weights and use [pos[l], pos[r]] intervals to query
// On [l,r], query the number of consecutive sons using [idx[rt[l]], idx[rt[r]]] interval
int pos[maxn], rt[maxn]; 
int tot_st; // Stack depth
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;
}