Description
一个合法的括号序列是这样定义的：
- 空串是合法的。
- 如果字符串
S是合法的，则(S)也是合法的。 - 如果字符串
A和B是合法的，则AB也是合法的。
现在给你一个长度为 (n) 的由 ( 和 ) 组成的字符串，位置标号从 (1) 到 (n) 。对这个字符串有下列四种操作：
Replace a b c：将 ([a,b]) 之间的所有括号改成 (c)。假设原来的字符串为：))())())(，那么执行操作 Replace 2 7 后原来的字符串变为：)(((((()(。
Swap a b：将 ([a,b]) 之间的字符串翻转。假设原来的字符串为：))())())(，那么执行操作 Swap 3 5 后原来的字符串变为：))))(())(。
Invert a b：将 ([a,b]) 之间的 ( 变成 ) ，) 变成 (。假设原来的字符串为：))())())(，那么执行操作 Invert 4 8 后原来的字符串变为：))((()(((。
Query a b：询问 ([a,b]) 之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的 ( 变成 ) 或 ) 变成 (。注意执行操作 Query 并不改变当前的括号序列。假设原来的字符串为：))())())(，那么执行操作 Query 3 6 的结果为 (2)，因为要将位置 (5) 的 ) 变成 ( 并将位置 (6) 的 ( 变成 )。
现给定 (n) 和这个字符串，以及 (q) 个操作，对于某一个 Query 询问输出答案。
Hint
(1le n,qle 10^5)
Solution
首先考虑一下如果做 Query 操作。
假如说，字符串为 ))())())((，那么配对的左右括号相互抵消，那么就成了：))))((。
若要将其改为合法的括号序列，显然要改成这样：(())()，一共改了 2 个 ( ，一个 )。可见是大概一般的左括号和右括号被修改了。
直接说结论：设 ( exttt{'('} = -1, exttt{')'} = 1)，令 ( ext{lmax, rmax, lmin, rmin}) 分别为最大前后缀和、最小前后缀和。
那么 ( ext{Query}(l, r) = leftlceil{ ext{lmax}(l, r) / 2} ight ceil + leftlceil{| ext{rmin}(l, r)| / 2} ight ceil) ，注意向上取整，以及最小后缀和需要取绝对值。
另外两个 ( ext{rmax, lmin}) 是辅助维护的，具体方法参考 SPOJ - GSS 系列题目。
如果没有 区间反转 可以 线段树，但现在只能 平衡树 了。时间复杂度 (O(nlog n))
下面是代码，把更新信息的操作写在函数里了，看得轻松一点。
Code
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : HNOI2011 JSOI2011 Luogu P3215 括号修复 / 括号序列
*/
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
const int N = 1e5 + 5;
int n, q;
int ch[N][2], fa[N], size[N];
int total = 0, root;
int lmax[N], rmax[N];
int lmin[N], rmin[N];
int sum[N], val[N];
int cov[N];
bool rev[N], flip[N];
inline int create(int c) {
int rt = ++ total;
val[rt] = sum[rt] = c;
size[rt] = 1;
if (c >= 0) {
lmax[rt] = rmax[rt] = c;
lmin[rt] = rmin[rt] = 0;
} else {
lmin[rt] = rmin[rt] = c;
lmax[rt] = rmax[rt] = 0;
}
return rt;
}
inline void pushup(int rt) {
int &l = ch[rt][0], &r = ch[rt][1];
sum[rt] = sum[l] + sum[r] + val[rt];
size[rt] = size[l] + size[r] + 1;
lmax[rt] = max(lmax[l], sum[l] + val[rt] + lmax[r]);
rmax[rt] = max(rmax[r], sum[r] + val[rt] + rmax[l]);
lmin[rt] = min(lmin[l], sum[l] + val[rt] + lmin[r]);
rmin[rt] = min(rmin[r], sum[r] + val[rt] + rmin[l]);
}
inline void updateRev(int rt) {
int &l = ch[rt][0], &r = ch[rt][1];
swap(l, r);
swap(lmax[rt], rmax[rt]);
swap(lmin[rt], rmin[rt]);
rev[rt] ^= 1;
}
inline void updateCov(int rt, int c) {
val[rt] = c, sum[rt] = c * size[rt];
if (c >= 0) {
lmin[rt] = rmin[rt] = 0;
lmax[rt] = rmax[rt] = sum[rt];
} else {
lmax[rt] = rmax[rt] = 0;
lmin[rt] = rmin[rt] = sum[rt];
}
cov[rt] = c;
}
inline void updateFlip(int rt) {
val[rt] = -val[rt], sum[rt] = -sum[rt];
int temp = lmax[rt];
lmax[rt] = -lmin[rt];
lmin[rt] = -temp;
temp = rmax[rt];
rmax[rt] = -rmin[rt];
rmin[rt] = -temp;
flip[rt] ^= 1;
cov[rt] = -cov[rt];
}
inline void pushdown(int rt) {
int &l = ch[rt][0], &r = ch[rt][1];
if (flip[rt]) {
if (l) updateFlip(l);
if (r) updateFlip(r);
flip[rt] = 0;
}
if (cov[rt]) {
if (l) updateCov(l, cov[rt]);
if (r) updateCov(r, cov[rt]);
cov[rt] = 0;
}
if (rev[rt]) {
if (l) updateRev(l);
if (r) updateRev(r);
rev[rt] = 0;
}
}
inline int get(int x) {
return x == ch[fa[x]][1];
}
inline void rotate(int x) {
int y = fa[x], z = fa[y], c = get(x);
ch[y][c] = ch[x][c ^ 1];
fa[ch[x][c ^ 1]] = y;
ch[x][c ^ 1] = y;
fa[y] = x, fa[x] = z;
if (z) ch[z][y == ch[z][1]] = x;
pushup(y), pushup(x);
}
inline void splay(int x, int g) {
for (register int f = fa[x]; (f = fa[x]) != g; rotate(x))
if (fa[f] != g) rotate(get(f) == get(x) ? f : x);
if (!g) root = x;
}
inline int select(int k) {
for (register int rt = root; ; ) {
pushdown(rt);
if (k == size[ch[rt][0]] + 1) return rt;
if (k < size[ch[rt][0]] + 1) rt = ch[rt][0];
else k -= size[ch[rt][0]] + 1, rt = ch[rt][1];
}
}
int ary[N];
int build(int l, int r, int f) {
if (l > r) return 0;
int mid = (l + r) >> 1, rt = create(ary[mid]);
val[rt] = ary[mid], fa[rt] = f;
ch[rt][0] = build(l, mid - 1, rt);
ch[rt][1] = build(mid + 1, r, rt);
return pushup(rt), rt;
}
inline void replace(int l, int r, int c) {
l = select(l), r = select(r + 2);
splay(l, 0), splay(r, l);
int x = ch[r][0];
updateCov(x, c);
pushup(r), pushup(l);
}
inline void reverse(int l, int r) {
l = select(l), r = select(r + 2);
splay(l, 0), splay(r, l);
int x = ch[r][0];
updateRev(x);
pushup(r), pushup(l);
}
inline void invert(int l, int r) {
l = select(l), r = select(r + 2);
splay(l, 0), splay(r, l);
int x = ch[r][0];
updateFlip(x);
pushup(r), pushup(l);
}
inline int query(int l, int r) {
l = select(l), r = select(r + 2);
splay(l, 0), splay(r, l);
int x = ch[r][0];
int p = lmax[x];
p = (p & 1) ? (p + 1) / 2 : p / 2;
int s = abs(rmin[x]);
s = (s & 1) ? (s + 1) / 2 : s / 2;
return p + s;
}
signed main() {
ios::sync_with_stdio(false);
int n, q; string s;
cin >> n >> q >> s;
for (register int i = 1; i <= n; i ++)
ary[i + 1] = (s[i - 1] == '(') ? -1 : 1;
ary[1] = ary[n + 2] = 0;
root = build(1, n + 2, 0);
while (q --) {
int l, r;
cin >> s;
if (s == "Replace") {
cin >> l >> r >> s;
replace(l, r, (s == "(") ? -1 : 1);
}
if (s == "Swap") {
cin >> l >> r;
reverse(l, r);
}
if (s == "Invert") {
cin >> l >> r;
invert(l, r);
}
if (s == "Query") {
cin >> l >> r;
cout << query(l, r) << '
';
}
}
}