[BZOJ2209][JSOI2011]括号序列(splay)

 1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=l; i<=r; i++) 4 using namespace std; 5 ?6 const int N=100010; 7 int n,m,op,rt,l,r,f[N],sz[N],v[N],sm[N],ch[N][2],lmn[N],rmn[N],lmx[N],rmx[N],rev[N],ops[N]; 8 char c; 9 10 void Rev(int x){ rev[x]^=1; swap(ch[x][0],ch[x][1]); swap(lmn[x],rmn[x]); swap(lmx[x],rmx[x]); }11 void Ops(int x){12 ????ops[x]^=1; sm[x]=-sm[x]; v[x]=-v[x];13 ????swap(lmn[x],lmx[x]); swap(rmn[x],rmx[x]);14 ????lmn[x]=-lmn[x]; rmn[x]=-rmn[x]; lmx[x]=-lmx[x]; rmx[x]=-rmx[x];15 }16 17 void push(int x){18 ????int l=ch[x][0],r=ch[x][1];19 ????if (rev[x]) Rev(l),Rev(r),rev[x]=0;20 ????if (ops[x]) Ops(l),Ops(r),ops[x]=0;21 }22 23 void upd(int x){24 ????int l=ch[x][0],r=ch[x][1];25 ????sz[x]=sz[l]+sz[r]+1; sm[x]=sm[l]+sm[r]+v[x];26 ????lmn[x]=min(lmn[l],sm[l]+v[x]+lmn[r]);27 ????lmx[x]=max(lmx[l],sm[l]+v[x]+lmx[r]);28 ????rmn[x]=min(rmn[r],sm[r]+v[x]+rmn[l]);29 ????rmx[x]=max(rmx[r],sm[r]+v[x]+rmx[l]);30 }31 32 void rot(int &rt,int x){33 ????int y=f[x],z=f[y],w=ch[y][1]==x;34 ????if (y==rt) rt=x; else ch[z][ch[z][1]==y]=x;35 ????f[x]=z; f[y]=x; f[ch[x][w^1]]=y;36 ????ch[y][w]=ch[x][w^1]; ch[x][w^1]=y; upd(y);37 }38 39 void splay(int &rt,int x){40 ????while (x!=rt){41 ????????int y=f[x],z=f[y];42 ????????if (y!=rt) rot(rt,((ch[z][1]==y)^(ch[y][1]==x)) ? x : y);43 ????????rot(rt,x);44 ????}45 ????upd(x);46 }47 48 int find(int x,int k){49 ????push(x); int l=ch[x][0],r=ch[x][1];50 ????if (k==sz[l]+1) return x;51 ????if (k<=sz[l]) return find(l,k); else return find(r,k-sz[l]-1);52 }53 54 int build(int L,int R){55 ????if (L>R) return 0;56 ????if (L==R){57 ????????sm[L]=v[L]; sz[L]=1;58 ????????if (v[L]==-1) lmn[L]=rmn[L]=-1;59 ????????if (v[L]==1) lmx[L]=rmx[L]=1;60 ????????return L;61 ????}62 ????int mid=(L+R)>>1;63 ????f[ch[mid][0]=build(L,mid-1)]=mid;64 ????f[ch[mid][1]=build(mid+1,R)]=mid;65 ????upd(mid); return mid;66 }67 68 int split(int l,int r){69 ????int x=find(rt,l),y=find(rt,r+2);70 ????splay(rt,x); splay(ch[x][1],y); return ch[y][0];71 }72 73 int main(){74 ????freopen("bzoj2209.in","r",stdin);75 ????freopen("bzoj2209.out","w",stdout);76 ????scanf("%d%d",&n,&m);77 ????rep(i,2,n+1) scanf(" %c",&c),v[i]=(c==‘(‘) ? 1 : -1;78 ????rt=build(1,n+2);79 ????rep(i,1,m){80 ????????scanf("%d%d%d",&op,&l,&r); int x=split(l,r);81 ????????if (op==0) printf("%d\n",(rmx[x]+1)/2-(lmn[x]-1)/2);82 ????????????else if (op==1) Ops(x); else Rev(x);83 ????}84 ????return 0;85 }