[括号] [计数] [树] CF1625E2 Cats on the Upgrade (hard version)

· · 题解

先说 E1 的做法。

显然对每个右括号求出其对应的左括号下标 lst_i，[lst_i,i] 是一段合法的括号子串，叫它们大串吧。

然后题目保证询问 [l,r] 可拆成若干个大串，答案就是这些大串拼成的方案数 + 大串内部的方案数。

这是个分治的形式，递推计算就好了。具体地，暴力找到 [lst_i,i] 内部的大串然后计算，预处理前缀和即可。

因为每个大串至多被算一次，所以复杂度 O(n)。

接着是 E2 的做法。

容易发现分治的过程呈树状。令 f_u 表示 [lst_u,u] 对应的大串内部方案数，不包括 u 本身。son_u 是 u 儿子集合。有转移 f_u=\frac {son_u\times(son_u+1)}2+\sum\limits_{v\in son_u} f_v。

那么修改是删除叶子，查询是求两个兄弟节点构成区间的方案数。

但是发现这玩意不好维护啊，如果树剖维护 f，那查询怎么办？

由于一次修改至多改变一个 son_u 是个很强的限制，所以将 f 展开，化成对 son 求和的形式方便处理。对于子树内节点 v，f_u=\sum \frac{son_v\times(son_v+1)}2。

用树状数组，修改操作是单点改，查询 f_u 是区间和。最后还要维护兄弟节点间有多少节点，再开个树状数组统计即可。

复杂度 O(n\log n)。

总结：主要难度在转化成树上问题、以及树上信息的维护，需要一定计数技巧。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 3e5 + 5;
int n, q, lst[N], nxt[N], stk[N], tp, opt, l, r;
int son[N], dfn[N], df, ed[N], _dfn[N], _df, fa[N], br[N];
char c[N];
vector<int> to[N];

struct BIT{
    int t[N];
    inline void init() {memset(t, 0, sizeof t);}
    inline void upd(int a, int k) {for(; a < N; a += a & -a) t[a] += k;}
    inline int qry(int a) {int res = 0; for(; a; a -= a & -a) res += t[a]; return res;}
    inline int fid(int l, int r) {if(l > r) return 0; return qry(r) - qry(l - 1);}
}A, B;
inline void dfs(int u){
    dfn[u] = ++df;
    for(auto v : to[u]) ++son[u], A.upd(_dfn[v] = ++_df, 1);
    for(auto v : to[u]) fa[v] = u, br[v] = df + 1, dfs(v);
    ed[u] = df, B.upd(dfn[u], son[u] * (son[u] + 1) / 2); 
}
signed main(){
    scanf("%lld%lld%s", &n, &q, c + 1);
    for(int i = 1; i <= n; ++i)
        if(c[i] == '(') stk[++tp] = i;
        else if(tp){
            lst[i] = stk[tp--], nxt[lst[i]] = i;
            int j = i - 1;
            while(j > lst[i]) to[i].push_back(j), j = lst[j] - 1;
            reverse(to[i].begin(), to[i].end());
        }
    for(int i = n, p = n + 1; i; --i) if(i <= p && lst[i]) p = lst[i], to[n + 1].push_back(i);
    reverse(to[n + 1].begin(), to[n + 1].end());
    dfs(n + 1);

    while(q--){
        scanf("%lld%lld%lld", &opt, &l, &r);
        if(opt == 1){
            A.upd(_dfn[r], -1);
            B.upd(dfn[fa[r]], son[fa[r]] * (son[fa[r]] - 1) / 2 - son[fa[r]] * (son[fa[r]] + 1) / 2), --son[fa[r]];
        }
        else{
            int res = B.fid(br[nxt[l]], ed[r]), cnt = A.fid(_dfn[nxt[l]], _dfn[r]);
            res += cnt * (cnt + 1) / 2;
            printf("%lld\n", res);
        }
    }
    return 0;
}