记录编号	409857	评测结果	AAAAAAAAAA
题目名称	[HNOI 2011] 括号修复	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.296 s
提交时间	2017-05-29 16:53:15	内存使用	9.26 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m;
char s[N];
int root,fa[N],son[N][2];
int v[N],sum[N],mal[N],mil[N],mar[N],mir[N],size[N];
int same[N];
bool rev[N],inv[N];
#define lc son[x][0]
#define rc son[x][1]
void update(int x){
	size[x]=size[lc]+size[rc]+1;
	sum[x]=sum[lc]+v[x]+sum[rc];
	mal[x]=max(mal[lc],sum[lc]+v[x]+mal[rc]);
	mil[x]=min(mil[lc],sum[lc]+v[x]+mil[rc]);
	mar[x]=max(mar[rc],sum[rc]+v[x]+mar[lc]);
	mir[x]=min(mir[rc],sum[rc]+v[x]+mir[lc]);
}
void makesame(int x,int val){
	v[x]=val;
	sum[x]=val*size[x];
	mal[x]=mar[x]=sum[x];
	mil[x]=mir[x]=0;
	if (val<0){
		swap(mal[x],mil[x]);
		swap(mar[x],mir[x]);
	}
	inv[x]=0;
	same[x]=val;
}
void invert(int x){
	v[x]=-v[x];
	sum[x]=-sum[x];
	mal[x]=-mal[x];
	mil[x]=-mil[x];
	swap(mal[x],mil[x]);
	mar[x]=-mar[x];
	mir[x]=-mir[x];
	swap(mar[x],mir[x]);
	if (same[x]) same[x]=-same[x];else inv[x]^=1;
}
void flip(int x){
	swap(lc,rc);
	swap(mal[x],mar[x]);
	swap(mil[x],mir[x]);
	rev[x]^=1;
}
void pushdown(int x){
	if (rev[x]){
		if (lc) flip(lc);
		if (rc) flip(rc);
		rev[x]=0;
	}
	if (same[x]){
		if (lc) makesame(lc,same[x]);
		if (rc) makesame(rc,same[x]);
		same[x]=0;
	}
	if (inv[x]){
		if (lc) invert(lc);
		if (rc) invert(rc);
		inv[x]=0;
	}
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (son[z][0]==y) son[z][0]=x;else
	if (son[z][1]==y) son[z][1]=x;
	update(y);update(x);
}
void splay(int x){
	for (;fa[x];rot(x)){
		int y=fa[x],z=fa[y];
		if (z&&fa[z]) rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
	root=x;
}
void find(int R){
	int x=root;
	while (1){
		pushdown(x);
		int i=size[lc]+1;
		if (i==R) return splay(x);
		if (R>i) R-=i,x=rc;else x=lc;
	}
}
int build(int l,int r){
	if (l>r) return 0;
	int x=(l+r)>>1;
	if (s[x]=='(') v[x]=1;
	if (s[x]==')') v[x]=-1;
	fa[lc=build(l,x-1)]=x;
	fa[rc=build(x+1,r)]=x;
	update(x);
	return x;
}
void print(int x){
	pushdown(x);
	if (lc) print(lc);
	if (v[x]==1) putchar('(');
	if (v[x]==-1) putchar(')'); 
	if (rc) print(rc);
}
char tp[10],c[10];
int main()
{
	freopen("brackets.in","r",stdin);
	freopen("brackets.out","w",stdout);
	scanf("%d%d%s",&n,&m,s+2);
	root=build(1,n+2);
	while (m--){
		int l,r;
		scanf("%s%d%d",tp,&l,&r);
		find(l);find(r+2);
		int now=son[son[root][0]][1];
		pushdown(now);
		if (tp[0]=='R'){
			scanf("%s",c);
			makesame(now,c[0]=='('?1:-1);
		}
		if (tp[0]=='Q'){
			int cnt=mil[now],ans=(1-cnt)/2;
			int S=sum[now]+ans*2;
			ans+=S/2;
			printf("%d\n",ans);
		}
		if (tp[0]=='S') flip(now);//,printf("opt %d is Swap\n",m);
		if (tp[0]=='I') invert(now);
		update(son[root][0]);
		update(root);
		//print(root);puts("");
	}
	return 0;
}