题意
给出一个括号序列，有四种操作：
1.将[l,r]的区间的括号都变成c
2.将[l,r]的区间括号序列翻转
3.将[l,r]的区间的括号取反
4.询问[l,r]区间至少需要翻转几个括号才能合法
100%的数据满足N,M≤100000N,M≤100000。
输入数据保证问题有解。
题解
对于一串不合法的括号序列我们可以先去掉配对的括号，那么他就变成'))(((('这样的形式，左边是一串')'，右边是一串'('，记')'的个数x，'('的个数y，x与y同奇偶（加起来是偶数），当是偶数时，他们各自可以进行内部改变，ans=x/2+y/2;当时奇数时，两边各剩下一个，他们都改变，ans=x/2+y/2+2;（都是下取整）
那么总结起来就是ans=(x+1)/2+(y+1)/2。（下取整）
那怎么去统计这个信息呢，应该是一种套路（我猜的）：把')'看做1，'('看做-1，那么最大前缀就是x，最小后缀就是-y。求最大前缀和最小后缀的方法和求最大子段和里面那个一样。
然后就可以做了，第一个操作维护覆盖标记cover；
第二个操作维护翻转标记res，因为要交换左右的最大最小值，左右需要四个值lmax,lmin,rmax,rmin，记得交换（lmax,rmax）,(lmin,rmin)。
第三个操作就相当于是区间乘以-1，这都是老套路了，在lmax,lmin,rmax,rmin都乘以-1之后，交换(lmin,lmax),(rmin,rmax)。
最后一个操作找到区间输出(lmax+1)/2+(-rmin+1)/2即可
要注意的就是标记下放，还是覆盖标记先，并且下放覆盖标记时，还要清掉下放目标的其他两个标记。
#include<bits/stdc++.h> using namespace std; const int maxn=100005; const int oo=100000; int n,m,root,num; int a[maxn]; char s[maxn],op[15]; struct Splay{ int fa,s[2],size,res,tag,cover; int val,lmax,lmin,rmax,rmin,sum; }tr[maxn]; template<class T>inline void read(T &x){ x=0;int f=0;char ch=getchar(); while(!isdigit(ch)) {f|=(ch=='-');ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x= f ? -x : x ; } int max(int x,int y){return x>y ? x : y ;} int min(int x,int y){return x<y ? x : y ;} void swap(int &x,int &y){int t=x;x=y;y=t;} void update(Splay &ret,Splay lx,Splay ry){ ret.size=lx.size+ry.size+1; ret.sum=lx.sum+ret.val+ry.sum; ret.lmax=max(lx.lmax,lx.sum+ret.val+ry.lmax); ret.rmax=max(ry.rmax,ry.sum+ret.val+lx.rmax); ret.lmin=min(lx.lmin,lx.sum+ret.val+ry.lmin); ret.rmin=min(ry.rmin,ry.sum+ret.val+lx.rmin); } void update(int now){ update(tr[now],tr[tr[now].s[0]],tr[tr[now].s[1]]); } int build(int l,int r,int f){ if(l>r) return 0; int now=++num,mid=(l+r)>>1; tr[now].fa=f; tr[now].val=a[mid]; tr[now].cover=oo; if(l==r){ tr[now].lmax=tr[now].rmax=max(0,tr[now].val); tr[now].lmin=tr[now].rmin=min(0,tr[now].val); tr[now].sum=tr[now].val; tr[now].size=1; return now; } tr[now].s[0]=build(l,mid-1,now); tr[now].s[1]=build(mid+1,r,now); update(now); return now; } void put_cover(int x,int val){ tr[x].res=tr[x].tag=0; tr[x].cover=tr[x].val=val; tr[x].sum=val*tr[x].size; tr[x].lmax=tr[x].rmax=max(0,tr[x].sum); tr[x].lmin=tr[x].rmin=min(0,tr[x].sum); } void put_res(int x){ if(!x) return ; tr[x].res^=1; swap(tr[x].s[0],tr[x].s[1]); swap(tr[x].lmax,tr[x].rmax); swap(tr[x].lmin,tr[x].rmin); } void put_tag(int x){ if(!x) return ; tr[x].tag^=1; tr[x].val*=-1; tr[x].sum*=-1; tr[x].lmax*=-1; tr[x].lmin*=-1; tr[x].rmax*=-1; tr[x].rmin*=-1; swap(tr[x].lmax,tr[x].lmin); swap(tr[x].rmax,tr[x].rmin); } void push_down(int x){ if(tr[x].cover!=oo){ put_cover(tr[x].s[0],tr[x].cover); put_cover(tr[x].s[1],tr[x].cover); tr[x].cover=oo; } if(tr[x].res){ put_res(tr[x].s[0]); put_res(tr[x].s[1]); tr[x].res=0; } if(tr[x].tag){ put_tag(tr[x].s[0]); put_tag(tr[x].s[1]); tr[x].tag=0; } } void debug(int x){ push_down(x); if(tr[x].s[0]) debug(tr[x].s[0]); printf("%d ",tr[x].val); if(tr[x].s[1]) debug(tr[x].s[1]); } int find(int k){ int now=root; while(1){ push_down(now); if(tr[tr[now].s[0]].size>=k) {now=tr[now].s[0];continue;} k-=tr[tr[now].s[0]].size; if(k==1) return now; k--; now=tr[now].s[1]; } } int get(int x){ return tr[tr[x].fa].s[1]==x; } void connect(int x,int y,int d){ tr[y].s[d]=x; tr[x].fa=y; } void rotate(int x){ int f=tr[x].fa,ff=tr[f].fa; int d1=get(x),d2=get(f); int cs=tr[x].s[d1^1]; connect(x,ff,d2); connect(f,x,d1^1); connect(cs,f,d1); update(f); update(x); } void splay(int x,int go){ if(go==root) root=x; go=tr[go].fa; while(tr[x].fa!=go){ int f=tr[x].fa; if(tr[f].fa==go) rotate(x); else if(get(x)==get(f)) {rotate(f);rotate(x);} else {rotate(x);rotate(x);} } } void replace(){ int l,r; read(l);read(r);scanf("%s",op); int x=find(l),y=find(r+2); splay(x,root); splay(y,tr[x].s[1]); //printf("%d %d ",x,y); put_cover(tr[y].s[0],op[0]==')' ? 1 : -1); //putchar(10); //debug(root); //putchar(10); update(y); update(x); } void reverse(){ int l,r; read(l);read(r); int x=find(l),y=find(r+2); splay(x,root); splay(y,tr[x].s[1]); put_res(tr[y].s[0]); update(y); update(x); } void invert(){ int l,r; read(l);read(r); int x=find(l),y=find(r+2); splay(x,root); splay(y,tr[x].s[1]); put_tag(tr[y].s[0]); update(y); update(x); } int query(){ int l,r; read(l);read(r); int x=find(l),y=find(r+2); splay(x,root); splay(y,tr[x].s[1]); int pos=tr[y].s[0]; //printf(" %d %d ",tr[pos].lmax,tr[pos].rmin); return ((tr[pos].lmax+1)>>1)+((-tr[pos].rmin+1)>>1); } int main(){ read(n);read(m); a[1]=-oo;a[n+2]=oo; scanf("%s",s+2);; for(int i=2;i<=n+1;i++) a[i]= s[i]==')' ? 1 : -1; root=build(1,n+2,0); for(int i=1;i<=m;i++){ scanf("%s",op); if(op[0]=='R') replace(); else if(op[0]=='S') reverse(); else if(op[0]=='I') invert(); else printf("%d ",query()); //putchar(10); //debug(root); //putchar(10); } }