Description

---

题解Here!

 

在$BZOJ$乱逛的时候看到了这题。

这不是$Splay$的沙茶题嘛？？？

于是顺手$1A$。。。

前三个操作打打标记乱搞搞就好了嘛。。。

不会的请先做这题：

对于操作4怎么整？

我们首先煮个栗子：

我们发现我们要求答案的括号序列一定长这个样：$)())()((())(()$

我们把其中所有的$()$删去：$))(($

是不是简单多了？！

我们的目标状态是$()()$。

设$1$为$($，$-1$为$)$。

将每段区间左侧不匹配的括号数和右侧不匹配的括号数记录下来，分别为$left[l,r]$和$right[l,r]$。

我们会发现：

一个匹配的括号序列中左括号数量等于右括号数量，一段化简后的序列的左侧右括号数量和右侧左括号数量，恰等于左右括号数量的前缀和以及后缀和。

于是对每一段区间，记录四个值：最小前缀和，最大前缀和，最小后缀和，最大后缀和。

然后记录：当前节点的值（$1$或$-1$），区间和，区间大小。

然后在$pushup,pushdown$的时候搞搞事就好了。

然后是计算答案。

对于所求区间，求$\frac{minl}{2}+\frac{maxr}{2}$，若$(minl\%2)\&(maxr\%2)==1$，即$minl,maxr$同为奇数，则还需加二，也就是额外的修改。

当然在代码里我用了个骚操作。。。

于是这道题就做完了。。。

然后我调了$2h$，就是因为把一个$1$打成了$0$，药丸。。。

附代码：

#include
      
       #include
       
        #include
        
         #define MAXN 100010using namespace std;int n,m,size=0,root;int val[MAXN];char ch[MAXN];struct Splay{	int f,s,rev,inv,c,son[2];	int v,sum,maxl,minl,maxr,minr;//v:	1 -> (			-1 -> )}a[MAXN];inline int read(){	int date=0,w=1;char c=0;	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}	return date*w;}inline int min(const int x,const int y){return x
         
          y?x:y;}inline void pushup(int rt){	if(!rt)return;	a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+1;	a[rt].sum=a[a[rt].son[0]].sum+a[a[rt].son[1]].sum+a[rt].v;	a[rt].maxl=max(a[a[rt].son[0]].maxl,a[a[rt].son[0]].sum+a[rt].v+a[a[rt].son[1]].maxl);	a[rt].minl=min(a[a[rt].son[0]].minl,a[a[rt].son[0]].sum+a[rt].v+a[a[rt].son[1]].minl);	a[rt].maxr=max(a[a[rt].son[1]].maxr,a[a[rt].son[1]].sum+a[rt].v+a[a[rt].son[0]].maxr);	a[rt].minr=min(a[a[rt].son[1]].minr,a[a[rt].son[1]].sum+a[rt].v+a[a[rt].son[0]].minr);}inline void pushdown_val(int rt,int c){	if(!rt)return;	a[rt].v=a[rt].c=c;	if(c==1){		a[rt].minl=a[rt].minr=0;		a[rt].maxl=a[rt].maxr=a[rt].sum=a[rt].s;	}	else{		a[rt].minl=a[rt].minr=a[rt].sum=-a[rt].s;		a[rt].maxl=a[rt].maxr=0;	}	a[rt].inv=0;}inline void pushdown_rev(int rt){	if(!rt)return;	a[rt].rev^=1;	swap(a[rt].son[0],a[rt].son[1]);	swap(a[rt].maxl,a[rt].maxr);swap(a[rt].minl,a[rt].minr);}inline void pushdown_inv(int rt){	if(!rt)return;	a[rt].inv^=1;	a[rt].v=-a[rt].v;a[rt].sum=-a[rt].sum;	a[rt].maxl=-a[rt].maxl;a[rt].minl=-a[rt].minl;	a[rt].maxr=-a[rt].maxr;a[rt].minr=-a[rt].minr;	swap(a[rt].maxl,a[rt].minl);swap(a[rt].maxr,a[rt].minr);}inline void pushdown(int rt){	if(!rt)return;	if(a[rt].rev){		pushdown_rev(a[rt].son[0]);		pushdown_rev(a[rt].son[1]);		a[rt].rev=0;	}	if(a[rt].c){		pushdown_val(a[rt].son[0],a[rt].c);		pushdown_val(a[rt].son[1],a[rt].c);		a[rt].c=0;	}	if(a[rt].inv){		pushdown_inv(a[rt].son[0]);		pushdown_inv(a[rt].son[1]);		a[rt].inv=0;	}}inline void turn(int rt,int k){	int x=a[rt].f,y=a[x].f;	pushdown(x);pushdown(rt);	a[x].son[k^1]=a[rt].son[k];	if(a[rt].son[k])a[a[rt].son[k]].f=x;	a[rt].f=y;	if(y)a[y].son[a[y].son[1]==x]=rt;	a[x].f=rt;	a[rt].son[k]=x;	pushup(x);pushup(rt);}void splay(int rt,int ancestry){	while(a[rt].f!=ancestry){		int x=a[rt].f,y=a[x].f;		if(y==ancestry)turn(rt,a[x].son[0]==rt);		else{			int k=a[y].son[0]==x?1:0;			if(a[x].son[k]==rt){turn(rt,k^1);turn(rt,k);}			else{turn(x,k);turn(rt,k);}		}	}	if(ancestry==0)root=rt;}inline int newnode(int x){	int rt=++size;	a[rt].son[0]=a[rt].son[1]=a[rt].f=0;	a[rt].c=a[rt].rev=a[rt].inv=0;	a[rt].s=1;	a[rt].v=a[rt].sum=val[x];	return rt;}int buildtree(int l,int r){	if(l>r)return 0;	int lson=0,rson=0,mid=l+r>>1;	lson=buildtree(l,mid-1);	int rt=newnode(mid);	rson=buildtree(mid+1,r);	a[rt].son[0]=lson;	a[rt].son[1]=rson;	if(lson)a[lson].f=rt;	if(rson)a[rson].f=rt;	pushup(rt);	return rt;}int kth(int rt,int k){	while(1){		pushdown(rt);		int y=a[rt].son[0];		if(k>a[y].s+1){			k-=a[y].s+1;			rt=a[rt].son[1];		}		else if(k<=a[y].s)rt=y;		else return rt;	}}inline void make_same(int l,int r,int k){	int front=kth(root,l),next=kth(root,r+2),q;	splay(front,0);splay(next,front);	q=a[next].son[0];	pushdown_val(q,k);	pushup(next);pushup(front);}inline void reverse(int l,int r){	int front=kth(root,l),next=kth(root,r+2),q;	splay(front,0);splay(next,front);	q=a[next].son[0];	pushdown_rev(q);	pushup(next);pushup(front);}inline void invert(int l,int r){	int front=kth(root,l),next=kth(root,r+2),q;	splay(front,0);splay(next,front);	q=a[next].son[0];	pushdown_inv(q);	pushup(next);pushup(front);}inline void query(int l,int r){	int front=kth(root,l),next=kth(root,r+2),q;	splay(front,0);splay(next,front);	q=a[next].son[0];	int ans=((a[q].maxr+1)>>1)-(a[q].minl-1)/2;	printf("%d\n",ans);}void work(){	char ch[10],k[2];	int x,y;	while(m--){		scanf("%s",ch);x=read();y=read();		switch(ch[0]){			case 'R':{				scanf("%s",k);				make_same(x,y,(k[0]==')'?-1:1));				break;			}			case 'S':{				reverse(x,y);				break;			}			case 'I':{				invert(x,y);				break;			}			case 'Q':{				query(x,y);				break;			}		}	}}void init(){	n=read();m=read();	scanf("%s",ch+2);	for(int i=2;i<=n+1;i++)val[i]=(ch[i]==')'?-1:1);	val[1]=val[n+2]=0;	root=buildtree(1,n+2);}int main(){	init();	work();    return 0;}