忻州集团网站建设,已收录的网站不好优化,网站筹备建设情况,网站之间如何交换友情链接题意
传送门 Codeforces 1625E2 Cats on the Upgrade (hard version)
题解
首先利用栈将原始字符串转换为合法的 RBS#xff0c;不能匹配的括号设为 ‘.’。根据匹配的括号序列构造树#xff0c;具体而言#xff0c;遇到左括号#xff0c;则新建节点向下递归#xff0c…题意
传送门 Codeforces 1625E2 Cats on the Upgrade (hard version)
题解
首先利用栈将原始字符串转换为合法的 RBS不能匹配的括号设为 ‘.’。根据匹配的括号序列构造树具体而言遇到左括号则新建节点向下递归遇到右括号则回溯。则对于括号树上某一结点 v v v子节点为 c h i ch_i chi其代表的合法括号序列 R B S v ( R B S c h 0 ) ( R B S c h 1 ) ⋯ RBS_v (RBS_{ch_0})(RBS_{ch_1})\cdots RBSv(RBSch0)(RBSch1)⋯
对于某棵子树的答案为子树的贡献加上 k ( k 1 ) / 2 k(k1)/2 k(k1)/2其中 k k k 为子树的数量后一项贡献代表了连续的 R B S c h RBS_{ch} RBSch 的枚举。操作 1 仅删除叶子节点与其双亲节点的连边那么使用 BIT 维护节点的贡献和以及每个节点的子树数量即可。总时间复杂度 O ( ( n q ) log n ) O\Big((n q)\log{n}\Big) O((nq)logn)。
#include bits/stdc.h
using namespace std;
using ll long long;
template typename T
struct BIT {vectorT 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;{vectorint 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();}}vectorvectorint g(1);vectorint vs(n), idx(n);{int pos 0;auto nxt []() {while (pos n s[pos] .) {pos 1;}return pos;};functionvoid(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();BITll bit;bit.init(m);vectorBITint v_bit(m);vectorint left(m), right(m);{int tm 0;functionvoid(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;
}
