设\(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;
}