CF1625E2 Cats on the Upgrade (hard version) 题解

题意：

本题和 CF1625E1 的唯一区别在于，本题有修改操作。

给定一个长度为 \(n\) 的仅包含 (、) 的字符串 \(s\)。给出如下定义：

定义某字符串是一个简单的合法括号序列，当且仅当我们可以通过若干次移除一个 . 或者一个连续的子串 () 的操作将这个字符串删空，且这个字符串不以 . 作为开头或者结尾。

定义 \(s[l\dots r]\) 为字符串 \(s\) 从第 \(l\) 个字符开始到第 \(r\) 个字符结束的子串。

定义 \(s_x\) 为字符串 \(s\) 的第 \(x\) 个字符。

一共有 \(q\) 次操作，每次操作分为如下两类：

1 l r：将 \(s_l\) 和 \(s_r\) 替换为 . 。保证 \(s[l\dots r]\) 以 ( 开头，以 ) 结尾，且中间所有字符都为 .。

2 l r：询问有多少个 \(s[l\dots r]\) 的子串是简单的 RBS。换句话说，请求出满足 \(l\le i\le j\le r\) 且 \(s[i\dots j]\) 是简单的 RBS 的 \((i,j)\) 的对数。保证 \(s[l\dots r]\) 是简单的合法括号序列。

数据范围：

\(2\le n\le 3\times 10^5,~1\le q\le 3\times 10^5,~1\le l<r\le n\)。

考虑将给定括号序列的树形结构建出来，并给每个点标个号。

设节点 \(u\) 有 \(s_u\) 个儿子，并设 \(f_u\) 为 \(u\) 的方案数，那么 \[ f_u = \frac{s_u(s_u+1)}{2} + \sum_{i \in \mathrm{SubTree}(u)} f_i \] 前面的是插板法考虑只选 \(u\) 的某一个连续儿子的情况，后面的是取某一部分。

这实际上询问就是求一段连续儿子的子树 \(f\) 的和。

由于修改操作对于 \(f\) 的影响体现在修改点的父节点上，那么这就是单点修改子树查询，考虑树状数组即可。

现在问题在于，如何求出两个兄弟节点之间有多少个节点。

考虑对每个节点开一个树状数组，大小为儿子的个数。

初始在每个儿子处插入 \(1\) ，每删掉一个儿子就把它在父节点的树状数组中的位置标为 \(0\)

那么区间查询就可以了。另外如果用线段树维护 \(f\) 的话，就能做 \(s[l\dots r]\) 不保证中间全为 . 的情况了

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(3e5 + 15))

struct BIT
{
    int n, *tr;
    void init(int len) { n = len; tr = new int[len + 1]; memset(tr, 0, (len + 1) * sizeof(tr[0])); }
    #define lowbit(x) ((x) & (-(x)))
    void add(int x, int v) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += v; }
    int qry(int x, int r = 0) { for(int i = x; i; i -= lowbit(i)) r += tr[i]; return r; }
    #undef lowbit
} S, T[N];
char s[N]; vector<int> vec[N];
int dfn[N], son[N], fa[N], ed[N], num[N];
int n, top, tot, stk[N], l[N], r[N], id[N], L[N], R[N];
void build(int u, int _l, int _r)
{
    rep(i, _l + 1, _r - 1) if(r[i])
    {
        vec[u].pb(++tot); L[tot] = i; R[tot] = r[i];
        id[i] = id[r[i]] = tot; build(tot, i, r[i]); i = r[i];
    }
}
void dfs(int u)
{
    static int tim = 0; dfn[u] = ++tim;
    for(int v : vec[u]) { num[v] = ++son[u], fa[v] = u, dfs(v); }
    ed[u] = tim; S.add(dfn[u], son[u] * (son[u] + 1) / 2);
    T[u].init(son[u]);
    for(int v : vec[u]) T[u].add(num[v], 1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int q; cin >> n >> q >> (s + 1);
    rep(i, 1, n)
    {
        if(s[i] == '(') stk[++top] = i;
        else if(s[i] == ')' && top > 0) { l[i] = stk[top], r[stk[top--]] = i; }
    }
    tot = 1;
    rep(i, 1, n) if(r[i])
    {
        vec[1].pb(++tot); L[tot] = i; R[tot] = r[i];
        id[i] = id[r[i]] = tot; build(tot, i, r[i]); i = r[i];
    }
    S.init(tot); dfs(1);
    for(int op, _l, _r, t; q; q--)
    {
        cin >> op >> _l >> _r;
        if(op == 1)
        {
            t = fa[id[_l]];
            S.add(dfn[t], son[t] * (son[t] - 1) / 2 - son[t] * (son[t] + 1) / 2);
            --son[t]; T[t].add(num[id[_l]], -1);
        }else
        {
            _l = id[_l], _r = id[_r], t = fa[_l]; 
            int nL = T[t].qry(num[_l]), nR = T[t].qry(num[_r]);
            cout << S.qry(ed[_r]) - S.qry(dfn[_l] - 1) + (nR - nL + 1) * (nR - nL + 2) / 2 << '\n';
        }
    }
    return 0;
}