题目大意：给定一个括号序列，提供四种操作：
1.将一段区间内的所有括号的变成'('或者')'
2.将一段区间反转
3.将一段区间内的所有括号翻转，即'('变成‘)'，')'变成'('
4.查询一段区间内要将至少多少个括号翻转才能变成一个合法的括号序列
(每次粘贴po姐姐的大意会不会告我侵权啊 害怕.jpg
这道题我到现在还没有A 微笑脸
我觉得splay的题完全没有办法调试啊，要到数据都该不对，肯定是我姿势不对 (┬＿┬)
先摆在这里好了 烦。。。
#include<bits/stdc++.h> #define ll long long using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();} return x*f; } #define N 100005 int n,m; int root,sz[N],sum[N],v[N],ch[N][2],lmx[N],rmx[N],lmn[N],rmn[N],fa[N],tag[N],tag2[N],tag3[N]; char s[N]; void pushup(int x){ int l=ch[x][0],r=ch[x][1]; sz[x]=sz[l]+sz[r]+1; sum[x]=sum[l]+sum[r]+v[x]; lmx[x]=max(lmx[l],sum[l]+v[x]+lmx[r]); rmx[x]=max(rmx[r],sum[r]+v[x]+rmx[l]); lmn[x]=min(lmn[l],sum[l]+v[x]+lmn[r]); rmn[x]=min(rmn[r],sum[r]+v[x]+rmn[r]); } void Swap(int x){ swap(lmn[x],rmn[x]);swap(lmx[x],rmx[x]); swap(ch[x][0],ch[x][1]); tag2[x]^=1; } void invert(int x){ lmn[x]=-lmn[x];rmn[x]=-rmn[x]; lmx[x]=-lmx[x];rmx[x]=-rmx[x]; swap(lmn[x],lmx[x]);swap(rmn[x],rmx[x]); v[x]=-v[x];sum[x]=-sum[x]; tag[x]=-tag[x];tag3[x]^=1; } void replace(int x,int w){ v[x]=w;sum[x]=sz[x]*w; if(w==1)lmx[x]=rmx[x]=sum[x],lmn[x]=rmn[x]=0; if(w==-1)lmn[x]=rmn[x]=sum[x],lmx[x]=rmx[x]=0; tag[x]=w;tag2[x]=0;tag3[x]=0; } void pushdown(int x){ if(tag2[x]){ if(ch[x][0])Swap(ch[x][0]); if(ch[x][1])Swap(ch[x][1]); tag2[x]=0; } if(tag3[x]){ if(ch[x][0])invert(ch[x][0]); if(ch[x][1])invert(ch[x][1]); tag3[x]=0; } if(tag[x]){ if(ch[x][0])replace(ch[x][0],tag[x]); if(ch[x][1])replace(ch[x][1],tag[x]); tag[x]=0; } } void Pushdown(int x){ if(fa[x])Pushdown(fa[x]); pushdown(x); } void rotate(int x,int &beto){ int y=fa[x],t=ch[y][1]==x; if(y!=beto)ch[fa[y]][ch[fa[y]][1]==y]=x;else beto=x; fa[x]=fa[y];fa[y]=x; fa[ch[x][!t]]=y; ch[y][t]=ch[x][!t]; ch[x][!t]=y; pushup(y);pushup(x); } void splay(int x,int &beto){ Pushdown(x); while(x!=beto){ int y=fa[x]; if(y!=beto){ if((ch[fa[y]][1]==y)==(ch[y][1]==x))rotate(y,beto); else rotate(x,beto); }rotate(x,beto); } } void build(int l,int r,int f){ int mid=l+r>>1; fa[mid]=f;if(mid<f)ch[f][0]=mid;else ch[f][1]=mid; if(l==r){ sz[l]=1;sum[l]=v[l]; if(v[l]==1)lmx[l]=rmx[l]=v[l]; if(v[l]==-1)lmn[l]=rmn[l]=v[l]; return; } if(l<mid)build(l,mid-1,mid); if(r>mid)build(mid+1,r,mid); pushup(mid); } int find_k(int x,int k){ pushdown(x); if(sz[ch[x][0]]==k-1)return x; if(sz[ch[x][0]]<k-1)return find_k(ch[x][1],k-sz[ch[x][0]]-1); return find_k(ch[x][0],k); } int main(){ freopen("test.in","r",stdin); // freopen("test.out","w",stdout); n=read();m=read();scanf("%s",s+2); n+=2; for(int i=2;i<n;i++)v[i]=s[i]=='('?1:-1; build(1,n,0);root=(1+n)>>1; // for(int i=1;i<=n;i++)cout<<i<<' '<<ch[i][0]<<' '<<ch[i][1]<<endl; // for(int i=1;i<=n;i++)cout<<i<<' '<<lmn[i]<<' '<<rmx[i]<<endl; // cout<<m<<"****************"<<endl; char p[10]; while(m--){ scanf("%s",s); int l=read(),r=read(); int x=find_k(root,l),y=find_k(root,r+2); splay(x,root);splay(y,ch[x][1]); int z=ch[y][0]; if(s[0]=='R'){ scanf("%s",p); if(p[0]=='(')replace(z,1); else replace(z,-1); } else if(s[0]=='S')Swap(z); else if(s[0]=='I')invert(z); else printf("%d ",(1-lmn[z])/2+(rmx[z]+1)/2); } return 0; } /* 4 5 (((( Re 1 2 ) Qu 1 2 S 2 3 I 3 4 Q 1 4 */
