题面
Sol
答案就是去掉匹配的括号后的左边右括号个数(/2)取下整和右边左括号个数(/2)取下整
维护：
设(()为(-1)，())为(1)，最大的前缀和就是左边右括号的个数
最小的的后缀和的相反数就是右边左括号的个数
因为要支持取反，翻转等操作
我们要维护左边最大最小，右边最大最小，子树和，子树大小
然后套(Splay)模板
# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
template <class Int>
IL void Input(RG Int &x){
RG int z = 1; RG char c = getchar(); x = 0;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= z;
}
const int maxn(1e5 + 5);
typedef int Arr[maxn];
int n, m, rt;
Arr lmn, rmn, lmx, rmx, size, val, sum, fa, inv, rev, cov, ch[2];
char s[maxn];
# define ls ch[0][x]
# define rs ch[1][x]
IL int Son(RG int x){
return ch[1][fa[x]] == x;
}
IL void Update(RG int x){
lmn[x] = min(lmn[ls], lmn[rs] + val[x] + sum[ls]);
lmx[x] = max(lmx[ls], lmx[rs] + val[x] + sum[ls]);
rmn[x] = min(rmn[rs], rmn[ls] + val[x] + sum[rs]);
rmx[x] = max(rmx[rs], rmx[ls] + val[x] + sum[rs]);
size[x] = size[ls] + size[rs] + 1;
sum[x] = sum[ls] + sum[rs] + val[x];
}
IL void Rotate(RG int x){
RG int y = fa[x], z = fa[y], c = Son(x);
if(z) ch[Son(y)][z] = x; fa[x] = z;
ch[c][y] = ch[!c][x], fa[ch[c][y]] = y;
ch[!c][x] = y, fa[y] = x;
Update(y);
}
IL void Splay(RG int x, RG int ff){
for(RG int y = fa[x]; y != ff; Rotate(x), y = fa[x])
if(fa[y] != ff) Son(x) ^ Son(y) ? Rotate(x) : Rotate(y);
if(!ff) rt = x;
Update(x);
}
IL void Build(RG int l, RG int r, RG int ff){
if(l > r) return;
RG int mid = (l + r) >> 1;
fa[mid] = ff;
if(ff) ch[ff < mid][ff] = mid;
else rt = mid;
Build(l, mid - 1, mid), Build(mid + 1, r, mid);
Update(mid);
}
IL void Invert(RG int x){
if(!x) return;
inv[x] ^= 1, sum[x] = -sum[x], val[x] = -val[x];
swap(lmx[x], lmn[x]), swap(rmx[x], rmn[x]);
lmx[x] = -lmx[x], rmx[x] = -rmx[x];
lmn[x] = -lmn[x], rmn[x] = -rmn[x];
}
IL void Cover(RG int x, RG int op){
if(!x) return;
cov[x] = op, inv[x] = rev[x] = 0;
sum[x] = op * size[x], val[x] = op;
lmx[x] = rmx[x] = max(0, sum[x]);
lmn[x] = rmn[x] = min(0, sum[x]);
}
IL void Reverse(RG int x){
if(!x) return;
rev[x] ^= 1, swap(ls, rs);
swap(lmx[x], rmx[x]), swap(lmn[x], rmn[x]);
}
IL void Pushdown(RG int x){
if(cov[x]) Cover(ls, cov[x]), Cover(rs, cov[x]), cov[x] = 0;
if(rev[x]) Reverse(ls), Reverse(rs), rev[x] ^= 1;
if(inv[x]) Invert(ls), Invert(rs), inv[x] ^= 1;
}
IL int Kth(RG int x, RG int k){
while(233){
RG int sz = size[ls];
Pushdown(x);
if(k <= sz) x = ls;
else if(k == sz + 1) return x;
else k -= sz + 1, x = rs;
}
}
IL int Split(RG int l, RG int r){
RG int x = Kth(rt, l); Splay(x, 0);
RG int y = Kth(rt, r + 2); Splay(y, x);
return ch[0][y];
}
char op[10], v;
int main(RG int argc, RG char* argv[]){
Input(n), Input(m), scanf(" %s", s + 2);
for(RG int i = 2; i <= n + 1; ++i) val[i] = s[i] == '(' ? -1 : 1;
Build(1, n + 2, 0);
for(RG int i = 1, l, r, x; i <= m; ++i){
scanf(" %s", op), Input(l), Input(r);
x = Split(l, r);
if(op[0] == 'R') scanf(" %c", &v), Cover(x, v == '(' ? -1 : 1);
else if(op[0] == 'S') Reverse(x);
else if(op[0] == 'I') Invert(x);
else printf("%d
", ((lmx[x] + 1) >> 1) + ((1 - rmn[x]) >> 1));
}
return 0;
}