题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=2209
题解：
Splay
很好的题，但是把智障的我给恶心到了。。。
首先不难发现，最后没有匹配的括号的样子一定是 ))))..((((...
即左边是右括号(设个数为nr)，右边是做括号(设个数为nl)
则答案为 ⌈nl÷2⌉ + ⌈nr÷2⌉ (⌈ ⌉：向上取整)
若把 ‘(‘ 看成 1，把 ‘)‘ 看成 -1，
那么在这个只含有 1 和 -1 的序列里，
前缀最小值的相反数就等于nr，
后缀最大值的就等于nl
所以对于询问操作来说，在Splay中记录：
key[x]（节点x是 1 还是 -1）
sum[x]（x子树对应区间的sum和）
pmn[x]（x子树对应区间的前缀最小值），
smx[x]（x子树对应区间的后缀最大值）。
对于第二个反转操作，
可以看出，只是把对应区间的 1→ -1，-1→ 1，
所以再多维护两个东西
pmx[x]（x子树对应区间的前缀最大值），
smn[x]（x子树对应区间的后缀最小值）。
然后把记录的 key[x],sum[x],pmn[x],pmx[x],smn[x],smx[x]全部取反（都乘上-1），
并且 swap(pmn[x],pmx[x]), swap(smn[x],smx[x])（因为取反了啊～）
再打个lazy标记，就好啦。
对于第三个翻转操作，
就只需交换左右子树，
并且 swap(pmx[x],smx[x])，swap(pmn[x],smn[x]) （只是把序列反了起来，所以交换前后缀信息即可）
然后打一个lazy标记。
因为lazy标记不存在先后影响，所以lazy下放时随便先放哪个都可以的。
代码：
#include<cstdio>#include<cstring>#include<iostream>#define MAXN 100500using namespace std;int N,M;struct SPT{int pmx[MAXN],pmn[MAXN],smx[MAXN],smn[MAXN],sum[MAXN],key[MAXN];int ch[MAXN][2],siz[MAXN],fa[MAXN],lazy[MAXN],rt;void Reverse(int x){sum[x]*=-1; key[x]*=-1;pmx[x]*=-1; pmn[x]*=-1; swap(pmx[x],pmn[x]);smx[x]*=-1; smn[x]*=-1; swap(smx[x],smn[x]);}void Flip(int x){swap(pmx[x],smx[x]);swap(pmn[x],smn[x]);swap(ch[x][0],ch[x][1]);}void Pushup(int x){siz[x]=siz[ch[x][0]]+1+siz[ch[x][1]];sum[x]=sum[ch[x][0]]+key[x]+sum[ch[x][1]];pmx[x]=max(pmx[ch[x][0]],sum[ch[x][0]]+key[x]+pmx[ch[x][1]]);pmn[x]=min(pmn[ch[x][0]],sum[ch[x][0]]+key[x]+pmn[ch[x][1]]); smx[x]=max(smx[ch[x][1]],sum[ch[x][1]]+key[x]+smx[ch[x][0]]);smn[x]=min(smn[ch[x][1]],sum[ch[x][1]]+key[x]+smn[ch[x][0]]);}void Pushdown(int x){if(lazy[x]&1){Reverse(ch[x][0]); lazy[ch[x][0]]^=1;Reverse(ch[x][1]); lazy[ch[x][1]]^=1;lazy[x]^=1;}if(lazy[x]&2){Flip(ch[x][0]); lazy[ch[x][0]]^=2;Flip(ch[x][1]); lazy[ch[x][1]]^=2;lazy[x]^=2;}}void Rotate(int x,int &k){static int y,z,l,r;y=fa[x]; z=fa[y];l=ch[y][0]!=x; r=l^1;if(!z) k=x;else ch[z][ch[z][0]!=y]=x;fa[ch[x][r]]=y; fa[y]=x; fa[x]=z;ch[y][l]=ch[x][r]; ch[x][r]=y;Pushup(y);}void Splay(int x,int &k){static int y,z;while(x!=k){y=fa[x]; z=fa[y];if(y!=k) (ch[z][0]!=y)^(ch[y][0]!=x)?Rotate(x,k):Rotate(y,k);Rotate(x,k);}Pushup(x);}int find(int x,int num){if(lazy[x]) Pushdown(x);if(num<=siz[ch[x][0]]) return find(ch[x][0],num);else if(num==siz[ch[x][0]]+1) return x;else return find(ch[x][1],num-siz[ch[x][0]]-1);}int Split(int l,int r){static int dl,dr;dl=find(rt,l); dr=find(rt,r+2);Splay(dl,rt); Splay(dr,ch[dl][1]);return ch[dr][0];}void Modify(int l,int r,int type){static int p;p=Split(l,r);if(type==1) Reverse(p);else Flip(p);lazy[p]^=type;Pushup(fa[p]); Pushup(fa[fa[p]]);}void Build(int &x,int dad,int l,int r){static char c;if(l>r) return;x=(l+r)>>1; fa[x]=dad;Build(ch[x][0],x,l,x-1);scanf(" %c",&c); key[x]=(c==‘(‘?1:-1);Build(ch[x][1],x,x+1,r);Pushup(x);}void BorderBuild(){rt=N+1;key[N+1]=0; key[N+2]=0;ch[N+1][1]=N+2; fa[N+2]=N+1;Build(ch[N+2][0],N+2,1,N);Pushup(N+2); Pushup(N+1);}int Query(int l,int r){static int p,ANS,nl,nr;p=Split(l,r);nl=-pmn[p]; nr=smx[p];ANS=(nl+1)/2+(nr+1)/2;return ANS;}}DT;int main(){freopen("/home/noilinux/Documents/模块学习/2209.in","r",stdin);scanf("%d%d",&N,&M);DT.BorderBuild();for(int i=1,c,l,r;i<=M;i++){scanf("%d%d%d",&c,&l,&r);if(c==0) printf("%d\n",DT.Query(l,r));else DT.Modify(l,r,c);}return 0;}
●BZOJ 2209 [Jsoi2011]括号序列
原文地址：http://www.cnblogs.com/zj75211/p/8108688.html