原文链接http://www.cnblogs.com/zhouzhendong/p/8093556.html
题目传送门 - BZOJ2209
题解
我太弱了，调出这题感觉都要吐了。
题解懒得写了。
给一个链接：
http://blog.csdn.net/lych_cys/article/details/50700277
代码
#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <cmath>using namespace std;const int N=100005;int fa[N],son[N][2],rev1[N],rev2[N],root;int Lmin[N],Lmax[N],Rmin[N],Rmax[N],sum[N],val[N],size[N];void pushup(int x){int ls=son[x][0],rs=son[x][1];sum[x]=sum[ls]+val[x]+sum[rs];size[x]=size[ls]+size[rs]+1;Lmin[x]=min(Lmin[ls],sum[ls]+val[x]+Lmin[rs]);Lmax[x]=max(Lmax[ls],sum[ls]+val[x]+Lmax[rs]);Rmin[x]=min(Rmin[rs],sum[rs]+val[x]+Rmin[ls]);Rmax[x]=max(Rmax[rs],sum[rs]+val[x]+Rmax[ls]);}int build(int pre,int L,int R){if (L>R)return 0;int mid=(L+R)>>1;fa[mid]=pre;if (L==R){Lmin[mid]=Rmin[mid]=Lmax[mid]=Rmax[mid]=0;sum[mid]=val[mid],size[mid]=1;if (val[mid]<0)Lmin[mid]=Rmin[mid]=-1;if (val[mid]>0)Lmax[mid]=Rmax[mid]=1;return mid;}son[mid][0]=build(mid,L,mid-1);son[mid][1]=build(mid,mid+1,R);pushup(mid);return mid;}void pushson(int x,int r1,int r2){if (!x)return;if (r1){rev1[x]^=1;swap(Lmin[x],Lmax[x]),Lmin[x]=-Lmin[x],Lmax[x]=-Lmax[x];swap(Rmin[x],Rmax[x]),Rmin[x]=-Rmin[x],Rmax[x]=-Rmax[x];sum[x]=-sum[x];val[x]=-val[x];}if (r2){rev2[x]^=1;swap(Lmin[x],Rmin[x]);swap(Lmax[x],Rmax[x]);swap(son[x][0],son[x][1]);}}void pushdown(int x){int &ls=son[x][0],&rs=son[x][1],&r1=rev1[x],&r2=rev2[x];pushson(ls,r1,r2);pushson(rs,r1,r2);r1=r2=0;}void pushadd(int x){if (fa[x])pushadd(fa[x]);pushdown(x);}int wson(int x){return son[fa[x]][1]==x;}void rotate(int x){if (!fa[x])return;int y=fa[x],z=fa[y],L=wson(x),R=L^1;if (z)son[z][wson(y)]=x;fa[x]=z,fa[y]=x,fa[son[x][R]]=y;son[y][L]=son[x][R],son[x][R]=y;pushup(y),pushup(x);}void splay(int x,int rt){if (!x)return;if (!rt)root=x;pushadd(x);for (int y=fa[x];fa[x]!=rt;rotate(x),y=fa[x])if (fa[y]!=rt)rotate(wson(x)==wson(y)?y:x);}int findkth(int x,int k){pushdown(x);if (size[son[x][0]]+1==k)return x;if (k<=size[son[x][0]])return findkth(son[x][0],k);elsereturn findkth(son[x][1],k-size[son[x][0]]-1);}int n,m;char str[N];int main(){scanf("%d%d%s",&n,&m,str+2);memset(val,0,sizeof val);for (int i=2;i<=n+1;i++)val[i]=str[i]==‘(‘?1:-1;root=build(0,1,n+2);for (int i=1;i<=m;i++){int op,x,y;scanf("%d%d%d",&op,&x,&y);x=findkth(root,x),y=findkth(root,y+2);splay(x,0);splay(y,x);int z=son[y][0];if (op==0)printf("%d\n",(Rmax[z]+1)/2-(Lmin[z]-1)/2);if (op==1)pushson(z,1,0);if (op==2)pushson(z,0,1);}return 0;}
BZOJ2209 [Jsoi2011]括号序列 splay
原文地址：http://www.cnblogs.com/zhouzhendong/p/8093556.html