Codeforces 1625E2 括号树 + BIT

题意

传送门 Codeforces 1625E2 Cats on the Upgrade (hard version)

题解

首先利用栈将原始字符串转换为合法的 RBS，不能匹配的括号设为 ‘.’。根据匹配的括号序列构造树，具体而言，遇到左括号，则新建节点向下递归，遇到右括号则回溯。则对于括号树上某一结点 $v$，子节点为 $c{h}_i$，其代表的合法括号序列 $RB{S}_v=(RB{S}_{c{h}_0})(RB{S}_{c{h}_1})\cdots$

对于某棵子树的答案，为子树的贡献，加上 $k(k+1)/2$，其中 $k$ 为子树的数量，后一项贡献代表了连续的 $RB{S}_{ch}$ 的枚举。操作 1 仅删除叶子节点与其双亲节点的连边，那么使用 BIT 维护节点的贡献和，以及每个节点的子树数量即可。总时间复杂度 $O((n+q)\log n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
struct BIT {vector<T> a;BIT() {}void init(int n) {a.resize(n + 1);}void add(int i, T x) {while (i < (int)a.size()) {a[i] += x;i += i & -i;}}T get(int i) {T s = 0;while (i > 0) {s += a[i];i -= i & -i;}return s;}
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, q;cin >> n >> q;string s;cin >> s;{vector<int> stk;for (int i = 0; i < n; ++i) {auto c = s[i];if (c == '(') {stk.push_back(i);} else {if (stk.empty()) {s[i] = '.';} else {stk.pop_back();}}}while (!stk.empty()) {s[stk.back()] = '.';stk.pop_back();}}vector<vector<int>> g(1);vector<int> vs(n), idx(n);{int pos = 0;auto nxt = [&]() {while (pos < n && s[pos] == '.') {pos += 1;}return pos;};function<void(int)> get = [&](int v) {while (nxt() < n && s[pos] == '(') {int u = g.size();g.push_back({});g[v].push_back(u);vs[pos] = v;idx[pos] = (int)g[v].size() - 1;pos += 1;get(u);nxt();vs[pos] = v;idx[pos] = (int)g[v].size() - 1;pos += 1;}};get(0);}int m = vs.size();BIT<ll> bit;bit.init(m);vector<BIT<int>> v_bit(m);vector<int> left(m), right(m);{int tm = 0;function<void(int)> dfs = [&](int v) {left[v] = tm;tm += 1;int k = g[v].size();v_bit[v].init(k);for (int i = 0; i < k; ++i) {v_bit[v].add(i + 1, 1);}bit.add(left[v] + 1, (ll)(k + 1) * k / 2);for (int u : g[v]) {dfs(u);}right[v] = tm;};dfs(0);}while (q--) {int op, l, r;cin >> op >> l >> r;l -= 1;r -= 1;assert(vs[l] == vs[r]);int v = vs[l];int a = idx[l], b = idx[r];if (op == 1) {bit.add(left[v] + 1, -v_bit[v].get((int)g[v].size()));v_bit[v].add(a + 1, -1);} else {ll res = bit.get(right[g[v][b]]) - bit.get(left[g[v][a]]);int k = v_bit[v].get(b + 1) - v_bit[v].get(a);res += (ll)(k + 1) * k / 2;cout << res << '\n';}}return 0;
}