题面
解析
要支持区间翻转，就可以想到Splay了
但是要维护什么信息才能得到答案呢，将 “)” 看作1，”(“ 看作-1，记前缀最大和为$lx$， 后缀最小和为$rn$，那么 $ans = left lceil frac{lx}{2} ight ceil + left lceil left | frac{rn}{2} ight | ight ceil$, 因此维护前缀最大和$lx$， 后缀最小和$rn$，但由于有区间翻转与取反操作，还需要维护前缀最小和$ln$， 后缀最大和$rx$，更新的方式与Splay求最大子段和时一样，如图：
可以求出答案了，但还有一件事需要考虑，就是标记与标记之间的影响，也就是标记下放时的先后顺序。显然覆盖标记需要先下放，它需要把儿子的翻转与取反标记清0；接下来是先翻转还是先取反呢？实际上两个标记之间没有影响，无论哪个第二个下放都行，我按照题目顺序，把翻转标记第二个下放，取反标记最后下放
代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<climits> using namespace std; const int maxn = 100006, inf = INT_MAX; template<class T> void read(T &re) { re=0; T sign=1; char tmp; while((tmp=getchar())&&(tmp<'0'||tmp>'9')) if(tmp=='-') sign=-1; re=tmp-'0'; while((tmp=getchar())&&(tmp>='0'&&tmp<='9')) re=(re<<3)+(re<<1)+(tmp-'0'); re*=sign; } int n, m, root; int a[maxn]; char ch[maxn]; struct splay_tree{ int s[2], fa, val, lx, rx, ln, rn, cov, rev, opp, sum, siz; }tr[maxn]; void Cover(int now, int x) { tr[now].val = x; tr[now].sum = tr[now].siz * tr[now].val; tr[now].lx = max(0, tr[now].sum); tr[now].rx = max(0, tr[now].sum); tr[now].ln = min(0, tr[now].sum); tr[now].rn = min(0, tr[now].sum); tr[now].cov = tr[now].val; tr[now].rev = tr[now].opp = 0; } void Reverse(int now) { swap(tr[now].s[0], tr[now].s[1]); swap(tr[now].lx, tr[now].rx); swap(tr[now].ln, tr[now].rn); tr[now].rev ^= 1; } void Oppsit(int now) { swap(tr[now].lx, tr[now].ln); swap(tr[now].rx, tr[now].rn); tr[now].lx *= -1; tr[now].rx *= -1; tr[now].ln *= -1; tr[now].rn *= -1; tr[now].val *= -1; tr[now].sum *= -1; tr[now].opp ^= 1; } void spread(int x) { int ls = tr[x].s[0], rs = tr[x].s[1]; if(tr[x].cov) { if(ls) Cover(ls, tr[x].cov); if(rs) Cover(rs, tr[x].cov); tr[x].cov = 0; } if(tr[x].rev) { if(ls) Reverse(ls); if(rs) Reverse(rs); tr[x].rev = 0; } if(tr[x].opp) { if(ls) Oppsit(ls); if(rs) Oppsit(rs); tr[x].opp = 0; } } void update(int x) { int ls = tr[x].s[0], rs = tr[x].s[1]; tr[x].sum = tr[ls].sum + tr[rs].sum + tr[x].val; tr[x].siz = tr[ls].siz + tr[rs].siz + 1; tr[x].lx = max(tr[ls].lx, tr[ls].sum + tr[x].val + tr[rs].lx); tr[x].rx = max(tr[rs].rx, tr[rs].sum + tr[x].val + tr[ls].rx); tr[x].ln = min(tr[ls].ln, tr[ls].sum + tr[x].val + tr[rs].ln); tr[x].rn = min(tr[rs].rn, tr[rs].sum + tr[x].val + tr[ls].rn); } void Rotate(int x) { int y = tr[x].fa, z = tr[y].fa, k = (tr[y].s[1] == x), w = (tr[z].s[1] == y), son = tr[x].s[k^1]; spread(y);spread(x); tr[y].s[k] = son;tr[son].fa = y; tr[x].s[k^1] = y;tr[y].fa = x; tr[z].s[w] = x;tr[x].fa = z; update(y);update(x); } void Splay(int x, int to) { int y, z; while(tr[x].fa != to) { y = tr[x].fa; z = tr[y].fa; if(z != to) Rotate((tr[y].s[0] == x) ^ (tr[z].s[0] == y)? x: y); Rotate(x); } if(!to) root = x; } void Build(int l, int r, int ff) { int mid = (l + r)>>1; if(l < mid) Build(l, mid - 1, mid); if(mid < r) Build(mid + 1, r, mid); if(ff) tr[ff].s[ff < mid] = mid; tr[mid].fa = ff; tr[mid].val = a[mid]; update(mid); } int Find(int x) { int now = root; while(1) { spread(now); int ls = tr[now].s[0], rs = tr[now].s[1]; if(tr[ls].siz + 1 == x) return now; if(x <= tr[ls].siz) now = ls; else x -= tr[ls].siz + 1, now = rs; } } int main() { read(n);read(m); scanf("%s", ch); for(int i = 1; i <= n; ++i) a[i+1] = (ch[i-1] == ')'? 1: -1); n += 2; Build(1, n, 0); tr[0].s[1] = root = (1 + n)>>1; for(int i = 1; i <= m; ++i) { //cout<<i<<endl; char opt[10]; scanf("%s", opt); if(opt[0] == 'R') { int x, y; char c[2]; read(x);read(y); scanf("%s", c); y += 2; x = Find(x); y = Find(y); Splay(x, 0); Splay(y, x); int now = tr[y].s[0]; Cover(now, (c[0] == ')'? 1: -1)); update(y);update(x); } else if(opt[0] == 'S') { int x, y; read(x);read(y); y += 2; x = Find(x); y = Find(y); Splay(x, 0); Splay(y, x); int now = tr[y].s[0]; Reverse(now); } else if(opt[0] == 'I') { int x, y; read(x);read(y); y += 2; x = Find(x); y = Find(y); Splay(x, 0); Splay(y, x); int now = tr[y].s[0]; Oppsit(now); update(y);update(x); } else { int x, y; read(x);read(y); y += 2; x = Find(x); y = Find(y); Splay(x, 0); Splay(y, x); int now = tr[y].s[0]; printf("%d ", (tr[now].lx + 1) / 2 + (abs(tr[now].rn) + 1) / 2); } } return 0; }