題意

傳送門 Codeforces 1625E2 Cats on the Upgrade (hard version)

題解

首先利用棧將原始字符串轉(zhuǎn)換為合法的 RBS，不能匹配的括號設(shè)為 ‘.’。根據(jù)匹配的括號序列構(gòu)造樹，具體而言，遇到左括號，則新建節(jié)點向下遞歸，遇到右括號則回溯。則對于括號樹上某一結(jié)點 $v$，子節(jié)點為 $c{h}_i$，其代表的合法括號序列 $RB{S}_v=(RB{S}_{c{h}_0})(RB{S}_{c{h}_1})?$

對于某棵子樹的答案，為子樹的貢獻，加上 $k(k+1)/2$，其中 $k$ 為子樹的數(shù)量，后一項貢獻代表了連續(xù)的 $RB{S}_{ch}$ 的枚舉。操作 1 僅刪除葉子節(jié)點與其雙親節(jié)點的連邊，那么使用 BIT 維護節(jié)點的貢獻和，以及每個節(jié)點的子樹數(shù)量即可。總時間復(fù)雜度 $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;
}