题意简述：
给一个括号序列，要求支持：
- 区间覆盖
- 区间取负
- 区间翻转
- 查询把一个区间改成合法括号序列最少改几位
思路：
先考虑静态的时候如何维护答案。
显然把所有合法的都删掉之后序列长这样：
))…)))(((…(())…)))(((…(())…)))(((…((
于是可以给(((赋值成−1-1−1，)))赋值成111，这样只用维护前缀最大值aaa和后缀最小值bbb。
然后就可以知道答案是⌊a+12⌋+⌊−b+12⌋\left\lfloor\frac{a+1}2\right\rfloor+\left\lfloor\frac{-b+1}2\right\rfloor⌊2a+1⌋+⌊2−b+1⌋，然后由于a+b=a+b=a+b=这段区间的和，因此实际上只用维护aaa。
于是用一个fhqtreapfhq_treapfhqtreap来支持上述修改即可。
代码：
#include<bits/stdc++.h>#define fi first#define se second#define ri register int#define gc getcharusing namespace std;inline int read(){ int ans=0; char ch=gc(); while(!isdigit(ch))ch=gc(); while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc(); return ans;}typedef pair<int,int> pii;const int N=1e5+5;int n,m;char s[N];inline unsigned int randd(){ static unsigned int x=23333; return x^=x<<13,x^=x>>17,x^=x<<5;}namespace fhq{ #define lc son[p][0] #define rc son[p][1] int siz[N],son[N][2],rd[N],cov[N],ls[N],rs[N],sum[N],val[N],rt=0,tot=0; bool rev[N],inv[N]; inline void pushup(int p){ ls[p]=max(ls[lc],sum[lc]+val[p]+ls[rc]); rs[p]=max(rs[rc],sum[rc]+val[p]+rs[lc]); siz[p]=siz[lc]+1+siz[rc]; sum[p]=sum[lc]+val[p]+sum[rc]; } inline void pushcov(int p,int v){ls[p]=rs[p]=max((int)(inv[p]=rev[p]=0),sum[p]=((cov[p]=val[p]=v)*siz[p]));} inline void pushrev(int p){rev[p]^=1,swap(ls[p],rs[p]),swap(lc,rc);} inline void pushinv(int p){inv[p]^=1,ls[p]-=sum[p],rs[p]-=sum[p],swap(ls[p],rs[p]),val[p]=-val[p],sum[p]=-sum[p];} inline void pushdown(int p){ if(cov[p])pushcov(lc,cov[p]),pushcov(rc,cov[p]),cov[p]=0; if(rev[p])pushrev(lc),pushrev(rc),rev[p]=0; if(inv[p])pushinv(lc),pushinv(rc),inv[p]=0; } inline int merge(int a,int b){ if(!a||!b)return a+b; pushdown(a),pushdown(b); if(rd[a]<rd[b])return son[a][1]=merge(son[a][1],b),pushup(a),a; return son[b][0]=merge(a,son[b][0]),pushup(b),b; } inline pii split(int p,int k){ if(!p)return pii(0,0); pii tmp; pushdown(p); if(siz[lc]>=k)return tmp=split(lc,k),lc=tmp.se,pushup(p),pii(tmp.fi,p); return tmp=split(rc,k-siz[lc]-1),rc=tmp.fi,pushup(p),pii(p,tmp.se); } inline void build(int&p,int l,int r){ if(l>r)return; int mid=l+r>>1; p=++tot; val[p]=sum[p]=s[mid]=='('?-1:1,rd[p]=randd(); if(l==r){ls[p]=rs[p]=max(0,val[p]),siz[p]=1;return;} build(lc,l,mid-1),build(rc,mid+1,r),pushup(p); } inline void cover(int l,int r,int v){ pii x=split(rt,l-1),y=split(x.se,r-l+1); pushcov(y.fi,v),rt=merge(x.fi,merge(y.fi,y.se)); } inline void reverse(int l,int r){ pii x=split(rt,l-1),y=split(x.se,r-l+1); pushrev(y.fi),rt=merge(x.fi,merge(y.fi,y.se)); } inline void invert(int l,int r){ pii x=split(rt,l-1),y=split(x.se,r-l+1); pushinv(y.fi),rt=merge(x.fi,merge(y.fi,y.se)); } inline void query(int l,int r){ pii x=split(rt,l-1),y=split(x.se,r-l+1); cout<<((ls[y.fi]+1)>>1)+((ls[y.fi]-sum[y.fi]+1)>>1)<<'\n',rt=merge(x.fi,merge(y.fi,y.se)); } #undef lc #undef rc}int main(){ n=read(),m=read(),scanf("%s",s+1); fhq::build(fhq::rt,1,n); char s[10],t[2]; for(ri l,r;m;--m){ scanf("%s",s),l=read(),r=read(); if(s[0]=='R'){ scanf("%s",t); fhq::cover(l,r,t[0]=='('?-1:1); } if(s[0]=='Q')fhq::query(l,r); if(s[0]=='I')fhq::invert(l,r); if(s[0]=='S')fhq::reverse(l,r); } return 0;}
