设\(nd[4]\)

0——多出来的右括号

1——多出来的左括号

2——取反后多出来的右括号

3——取反后多出来的左括号

这样一来

Swap: swap(0,3),swap(1,2),swap(sn[0],sn[1])

Invert: swap(0,2),swap(1,3),val[k]^=1

Replace: v<-siz[k],v+2^1<-siz[k],v^1<-0,v+2<-0

注意一下运算优先级就好

#include"cstdio"

#include"cstring"

#include"iostream"

#include"algorithm"

using namespace std;

const int MAXN=1e5+5;

int n,m,cnt,root;

char ch[MAXN];

int val[MAXN],rev[MAXN],sn[2][MAXN],siz[MAXN];

int nd[4][MAXN],tag3[MAXN];

bool tag1[MAXN],tag2[MAXN];

int cret(int v)

{

	int tmp=++cnt;

	siz[tmp]=1;

	val[tmp]=v;

	tag3[tmp]=-1;

	nd[v][tmp]=nd[v+2^1][tmp]=1;

	rev[tmp]=rand();

	return tmp;

}

void pushdown(int k)

{

	if(tag3[k]!=-1){

		if(sn[0][k]) nd[tag3[k]][sn[0][k]]=nd[tag3[k]+2^1][sn[0][k]]=siz[sn[0][k]],nd[tag3[k]^1][sn[0][k]]=nd[tag3[k]+2][sn[0][k]]=0,val[sn[0][k]]=tag3[sn[0][k]]=tag3[k],tag1[sn[0][k]]=tag2[sn[0][k]]=0;

		if(sn[1][k]) nd[tag3[k]][sn[1][k]]=nd[tag3[k]+2^1][sn[1][k]]=siz[sn[1][k]],nd[tag3[k]^1][sn[1][k]]=nd[tag3[k]+2][sn[1][k]]=0,val[sn[1][k]]=tag3[sn[1][k]]=tag3[k],tag1[sn[1][k]]=tag2[sn[1][k]]=0;

	}if(tag2[k]){

		swap(sn[0][k],sn[1][k]);

		if(sn[0][k]) swap(nd[0][sn[0][k]],nd[3][sn[0][k]]),swap(nd[1][sn[0][k]],nd[2][sn[0][k]]),tag2[sn[0][k]]^=1;

		if(sn[1][k]) swap(nd[0][sn[1][k]],nd[3][sn[1][k]]),swap(nd[1][sn[1][k]],nd[2][sn[1][k]]),tag2[sn[1][k]]^=1;

	}if(tag1[k]){

		if(sn[0][k]) swap(nd[0][sn[0][k]],nd[2][sn[0][k]]),swap(nd[1][sn[0][k]],nd[3][sn[0][k]]),tag1[sn[0][k]]^=1,val[sn[0][k]]^=1;

		if(sn[1][k]) swap(nd[0][sn[1][k]],nd[2][sn[1][k]]),swap(nd[1][sn[1][k]],nd[3][sn[1][k]]),tag1[sn[1][k]]^=1,val[sn[1][k]]^=1;

	}tag1[k]=tag2[k]=0;

	tag3[k]=-1;

	return;

}

void pushup(int k)

{

	siz[k]=siz[sn[0][k]]+siz[sn[1][k]]+1;

	nd[0][k]=nd[0][sn[0][k]];

	nd[1][k]=nd[1][sn[1][k]];

	int tmp=nd[1][sn[0][k]]-nd[0][sn[1][k]];

	tmp+=val[k]?1:-1;

	if(tmp>0) nd[1][k]+=tmp;

	else nd[0][k]-=tmp;

	nd[2][k]=nd[2][sn[0][k]];

	nd[3][k]=nd[3][sn[1][k]];

	tmp=nd[3][sn[0][k]]-nd[2][sn[1][k]];

	tmp+=val[k]?-1:1;

	if(tmp>0) nd[3][k]+=tmp;

	else nd[2][k]-=tmp;

	return;

}

void dro(int k,int v,int &x,int &y)

{

	if(!k){x=y=0;return;}

	pushdown(k);

	if(siz[sn[0][k]]<v) x=k,dro(sn[1][k],v-siz[sn[0][k]]-1,sn[1][k],y);

	else y=k,dro(sn[0][k],v,x,sn[0][k]);

	pushup(k);

	return;

}

int un(int x,int y)

{

	if(!x||!y) return x|y;

	if(rev[x]<rev[y]){

		pushdown(x);

		sn[1][x]=un(sn[1][x],y);

		pushup(x);

		return x;

	}pushdown(y);

	sn[0][y]=un(x,sn[0][y]);

	pushup(y);

	return y;

}

void slv0(int l,int r)

{

	int x,y,z;

	dro(root,r,x,z);

	dro(x,l-1,x,y);

	printf("%d\n",(nd[0][y]+1)/2+(nd[1][y]+1)/2);

	root=un(un(x,y),z);

	return;

}

void slv1(int l,int r)

{

	int x,y,z;

	dro(root,r,x,z);

	dro(x,l-1,x,y);

	tag1[y]^=1;val[y]^=1;

	pushdown(y);pushup(y);

	root=un(un(x,y),z);

	return;

}

void slv2(int l,int r)

{

	int x,y,z;

	dro(root,r,x,z);

	dro(x,l-1,x,y);

	tag2[y]^=1;

	pushdown(y);pushup(y);

	root=un(un(x,y),z);

	return;

}

void slv3(int l,int r,int kd)

{

	int x,y,z;

	dro(root,r,x,z);

	dro(x,l-1,x,y);

	tag3[y]=val[y]=kd;tag1[y]=tag2[y]=0;

	pushdown(y);pushup(y);

	root=un(un(x,y),z);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	scanf("%s",ch+1);

	for(int i=1;i<=n;++i) root=un(root,cret(ch[i]=='('));

	while(m--){

		int l,r;

		scanf("%s%d%d",ch+1,&l,&r);

		if(ch[1]=='Q') slv0(l,r);

		else if(ch[1]=='I') slv1(l,r);

		else if(ch[1]=='S') slv2(l,r);

		else scanf("%s",ch+1),slv3(l,r,ch[1]=='(');

	}return 0;

}