好恶心的数据结构题。
考虑单个询问。把(视作1，把)视作-1，设minprefix为最小前缀和，设cp=(minprefix+1)/2，那么答案为(sum/2+cp*2)，使劲想想想得出来。
所以就是用个splay或者smt来维护一下一段的最小前缀和以及总和。因为有两种操作所以写起来比较麻烦。要注意不要把操作看反了，还要注意标记的优先级和更新的问题。
恶心了一下午。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct dat {
int sm, t[2][2];
inline void operator =(const dat& a) {
sm = a. sm;
t[0][0] = a. t[0][0];
t[0][1] = a. t[0][1];
t[1][0] = a. t[1][0];
t[1][1] = a. t[1][1];
}
};
const int maxn = 100009;
int n, m, cr, a[maxn], sz[maxn], ls[maxn], rs[maxn], pt[maxn], vl[maxn];
bool flip[maxn], rev[maxn];
dat d[maxn];
dat sgd(int v) {
dat r;
r. sm = v;
r. t[0][0] = min(v, 0);
r. t[1][0] = r. t[0][0];
r. t[0][1] = min(-v, 0);
r. t[1][1] = r. t[0][1];
return r;
}
dat mgd(const dat& a, const dat& b) {
dat r;
r. sm = a. sm + b. sm;
r. t[0][0] = min(a. t[0][0], a. sm + b. t[0][0]);
r. t[1][0] = min(b. t[1][0], b. sm + a. t[1][0]);
r. t[0][1] = min(a. t[0][1], -a. sm + b. t[0][1]);
r. t[1][1] = min(b. t[1][1], -b. sm + a. t[1][1]);
return r;
}
inline void fix(int p) {
if (flip[p]) {
swap(ls[p], rs[p]);
swap(d[p]. t[0][0], d[p]. t[1][0]);
swap(d[p]. t[0][1], d[p]. t[1][1]);
if (ls[p])
flip[ls[p]] ^= 1;
if (rs[p])
flip[rs[p]] ^= 1;
flip[p] = 0;
}
}
inline void reverse(dat& r) {
swap(r. t[0][0], r. t[0][1]);
swap(r. t[1][0], r. t[1][1]);
r. sm = -r. sm;
}
inline void pushDown(int p) {
if (rev[p]) {
if (ls[p]) {
rev[ls[p]] ^= 1;
reverse(d[ls[p]]);
}
if (rs[p]) {
rev[rs[p]] ^= 1;
reverse(d[rs[p]]);
}
vl[p] = -vl[p];
rev[p] = 0;
}
}
inline void update(int p) {
sz[p] = sz[ls[p]] + sz[rs[p]] + 1;
d[p] = sgd(rev[p] ? -vl[p] : vl[p]);
if (ls[p]) {
fix(ls[p]);
d[p] = mgd(d[ls[p]], d[p]);
}
if (rs[p]) {
fix(rs[p]);
d[p] = mgd(d[p], d[rs[p]]);
}
if (rev[p])
reverse(d[p]);
}
inline void lRot(int q) {
int p = pt[q], a = pt[p];
if (rs[q])
pt[rs[q]] = p;
ls[p] = rs[q];
rs[q] = p;
pt[q] = a;
pt[p] = q;
if (a) {
if (p == ls[a])
ls[a] = q;
else
rs[a] = q;
}
update(p);
update(q);
}
inline void rRot(int q) {
int p = pt[q], a = pt[p];
if (ls[q])
pt[ls[q]] = p;
rs[p] = ls[q];
ls[q] = p;
pt[q] = a;
pt[p] = q;
if (a) {
if (p == ls[a])
ls[a] = q;
else
rs[a] = q;
}
update(p);
update(q);
}
void splay(int q) {
static int stc[maxn];
int tst = 1;
stc[tst] = q;
while (pt[stc[tst]]) {
stc[tst + 1] = pt[stc[tst]];
++ tst;
}
while (tst) {
fix(stc[tst]);
pushDown(stc[tst]);
-- tst;
}
while (pt[q]) {
int p = pt[q], a = pt[p];
if (!a || !pt[a]) {
if (q == ls[p])
lRot(q);
else
rRot(q);
}
else {
if (p == ls[a]) {
if (q == ls[p])
lRot(p), lRot(q);
else
rRot(q), lRot(q);
}
else {
if (q == ls[p])
lRot(q), rRot(q);
else
rRot(p), rRot(q);
}
}
}
cr = q;
}
int buildTree(int l, int r) {
if (l > r)
return 0;
int p = (l + r) >> 1;
ls[p] = buildTree(l, p - 1);
if (ls[p])
pt[ls[p]] = p;
rs[p] = buildTree(p + 1, r);
if (rs[p])
pt[rs[p]] = p;
sz[p] = sz[ls[p]] + sz[rs[p]] + 1;
rev[p] = 0;
flip[p] = 0;
vl[p] = a[p];
update(p);
return p;
}
int kth(int p, int k) {
while (p) {
fix(p);
if (sz[ls[p]] + 1 == k)
break;
else if (sz[ls[p]] + 1 > k)
p = ls[p];
else
k -= sz[ls[p]] + 1, p = rs[p];
}
return p;
}
int getRange(int l, int r) {
if (l == 1 && r == n)
return cr;
else if (l == 1) {
int p = kth(cr, r + 1);
splay(p);
return ls[p];
}
else if (r == n) {
int p = kth(cr, l - 1);
splay(p);
return rs[p];
}
else {
int p = kth(cr, l - 1), q = kth(cr, r + 1);
splay(p);
splay(q);
return rs[p];
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
memset(flip, 0, sizeof(flip));
memset(rev, 0, sizeof(rev));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i) {
int g;
do
g = getchar();
while (g != '(' && g != ')');
a[i] = (g == '(') ? 1 : -1;
}
cr = buildTree(1, n);
while (m --) {
int opt, l, r;
scanf("%d%d%d", &opt, &l, &r);
if (opt == 0) {
int x = getRange(l, r);
fix(x);
pushDown(x);
update(x);
printf("%d\n", (d[x]. sm >> 1) + ((-d[x]. t[0][0] + 1) & ~1));
}
else if (opt == 2) {
int x = getRange(l, r);
flip[x] ^= 1;
splay(x);
}
else if (opt == 1) {
int x = getRange(l, r);
rev[x] ^= 1;
reverse(d[x]);
splay(x);
}
}
}