一开始以为可以直接线段树的，好像还是不行……还是得用Spaly，然后就没啥了。
#include<cstdio> #include<algorithm> #define MN 210000 using namespace std; inline int read(){ int ca=getchar(),p=0; while (ca<'0'||ca>'9') ca=getchar(); while (ca>='0'&&ca<='9') p=p*10+ca-48,ca=getchar(); return p; } struct na{int s,qm,qi,hm,hi;na(int _s=0,int _qm=0,int _qi=0,int _hm=0,int _hi=0):s(_s),qm(_qm),qi(_qi),hm(_hm),hi(_hi){};}; struct tree{ int f,c[2],k,s,S; na w; bool rev,cg; }t[MN]; char s[MN]; int n,m,num=0,st[MN],top,root,l,r; na hb(na a,na b){ na c; c.s=a.s+b.s; c.qm=max(a.qm,b.qm+a.s); c.qi=min(a.qi,b.qi+a.s); c.hm=max(b.hm,a.hm+b.s); c.hi=min(b.hi,a.hi+b.s); return c; } inline void REV(int p){ if (!p) return; t[p].w=na(t[p].w.s,t[p].w.hm,t[p].w.hi,t[p].w.qm,t[p].w.qi); swap(t[p].c[0],t[p].c[1]); t[p].rev^=1; } inline void REP(int p,int s){ if (!p) return;t[p].k=s;t[p].rev=t[p].cg=0; if (s==1) t[p].w=na(t[p].S,t[p].S,0,t[p].S,0);else t[p].w=na(-t[p].S,0,-t[p].S,0,-t[p].S); t[p].s=s; } inline void CG(int p){ if (!p) return; t[p].cg^=1;t[p].k*=-1; t[p].w=na(-t[p].w.s,-t[p].w.qi,-t[p].w.qm,-t[p].w.hi,-t[p].w.hm); } inline void gx(int p){ if (t[p].k==1) t[p].w=na(1,1,0,1,0);else t[p].w=na(-1,0,-1,0,-1); if (t[p].c[0])t[p].w=hb(t[t[p].c[0]].w,t[p].w); if (t[p].c[1])t[p].w=hb(t[p].w,t[t[p].c[1]].w); t[p].S=t[t[p].c[0]].S+t[t[p].c[1]].S+1; } inline void pd(int p){ if (t[p].s) REP(t[p].c[0],t[p].s),REP(t[p].c[1],t[p].s),t[p].s=0; if (t[p].rev) REV(t[p].c[0]),REV(t[p].c[1]),t[p].rev=0; if (t[p].cg) CG(t[p].c[0]),CG(t[p].c[1]),t[p].cg=0; } void build(int &p,int l,int r){ if (l>r) return; int mid=l+r>>1; p=mid+1;t[p].s=t[p].rev=0; if (s[mid]=='(') t[p].k=1;else t[p].k=-1; build(t[p].c[0],l,mid-1);build(t[p].c[1],mid+1,r); t[t[p].c[0]].f=t[t[p].c[1]].f=p; gx(p); } void rot(int &p,bool bo){ int k=t[p].c[bo]; t[p].c[bo]=t[k].c[!bo]; t[k].c[!bo]=p; t[t[p].c[bo]].f=p; t[k].f=t[p].f; t[p].f=k; gx(p);gx(k); p=k; } inline bool gc(int p){return t[t[p].f].c[1]==p;} inline void ph(int p){if (t[p].f==root) rot(root,gc(p));else rot(t[t[t[p].f].f].c[gc(t[p].f)],gc(p));} void spaly(int p,int f){ top=0; for (int i=p;i;i=t[i].f) st[++top]=i; while (top) pd(st[top--]); while (t[p].f!=f) if (t[t[p].f].f==f) ph(p);else if (gc(p)==gc(t[p].f)) ph(t[p].f),ph(p);else ph(p),ph(p); } int fi(int p,int k){ pd(p); if (t[t[p].c[0]].S>=k) return fi(t[p].c[0],k);else if (t[t[p].c[0]].S+1==k) return p;else return fi(t[p].c[1],k-1-t[t[p].c[0]].S); } inline void rep(){ int l,r; l=fi(root,read());r=fi(root,read()+2);scanf("%s",s); spaly(l,0);spaly(r,l); REP(t[r].c[0],s[0]=='('?1:-1); } inline void sw(){ int l,r; l=fi(root,read());r=fi(root,read()+2); spaly(l,0);spaly(r,l); REV(t[r].c[0]); } inline void cg(){ int l,r; l=fi(root,read());r=fi(root,read()+2); spaly(l,0);spaly(r,l); CG(t[r].c[0]); } inline void que(){ int l,r; l=fi(root,read());r=fi(root,read()+2); spaly(l,0);spaly(r,l); printf("%d\n",(t[t[r].c[0]].w.hm+1>>1)+(-t[t[r].c[0]].w.qi+1>>1)); } int main(){ n=read();m=read(); scanf("%s",s+1); build(root,0,n+1); while (m--){ scanf("%s",s); if (s[0]=='R') rep();else if (s[0]=='S') sw();else if (s[0]=='I') cg();else que(); } }