【传送门：BZOJ2209】
简要题意：
给出一个长度为n的括号序列，有q个操作，3种操作：
0 l r求出最少的步数，每步可以改变一个括号，将l到r的括号序列变为一一配对（也就是左括号在右边总有一个右括号与之对应）
1 l r将l到r中的左括号变成右括号，右括号变成左括号
2 l r将l到r的序列翻转
题解：
SPLAY
对于一个括号序列，将左括号看成1，右括号看成-1
最少的步数为一段序列中：(最小前缀和的绝对值+1)/2+(最大后缀和+1)/2
这样子就要维护最小前缀和和最大后缀和，还要维护最小后缀和和最大前缀和（为了方便修改）
然后因为两个改变操作不会互相影响，所以下放标记的时候顺序随意
因为小细节，调了一下午和一晚上，心累
参考代码：
#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>using namespace std;struct node{ ???int son[2],f,c,s,d; ???int ln,rn,lm,rm; ???bool fz,zf;}tr[110000];int len,root;void fanzhuan(int x){ ???tr[x].fz=false; ???swap(tr[x].son[0],tr[x].son[1]); ???int lc=tr[x].son[0],rc=tr[x].son[1]; ???if(lc!=0) ???{ ???????swap(tr[lc].ln,tr[lc].rn); ???????swap(tr[lc].lm,tr[lc].rm); ???????tr[lc].fz^=1; ???} ???if(rc!=0) ???{ ???????????swap(tr[rc].ln,tr[rc].rn); ???????swap(tr[rc].lm,tr[rc].rm); ???????tr[rc].fz^=1; ???}}void zhuanfan(int x){ ???tr[x].zf=false; ???int lc=tr[x].son[0],rc=tr[x].son[1]; ???if(lc!=0) ???{ ???????tr[lc].ln=-tr[lc].ln;tr[lc].lm=-tr[lc].lm; ???????swap(tr[lc].ln,tr[lc].lm); ???????tr[lc].rn=-tr[lc].rn;tr[lc].rm=-tr[lc].rm; ???????swap(tr[lc].rn,tr[lc].rm); ???????tr[lc].s=-tr[lc].s;tr[lc].d=-tr[lc].d; ???????tr[lc].zf^=1; ???} ???if(rc!=0) ???{ ???????tr[rc].ln=-tr[rc].ln;tr[rc].lm=-tr[rc].lm; ???????swap(tr[rc].ln,tr[rc].lm); ???????tr[rc].rn=-tr[rc].rn;tr[rc].rm=-tr[rc].rm; ???????swap(tr[rc].rn,tr[rc].rm); ???????tr[rc].s=-tr[rc].s;tr[rc].d=-tr[rc].d; ???????tr[rc].zf^=1; ???}}void update(int x){ ???int lc=tr[x].son[0],rc=tr[x].son[1]; ???tr[x].c=tr[lc].c+tr[rc].c+1; ???tr[x].s=tr[lc].s+tr[rc].s+tr[x].d; ???tr[x].ln=min(tr[lc].s+tr[rc].ln+tr[x].d,tr[lc].ln); ???tr[x].lm=max(tr[lc].s+tr[rc].lm+tr[x].d,tr[lc].lm); ???tr[x].rn=min(tr[lc].rn+tr[rc].s+tr[x].d,tr[rc].rn); ???tr[x].rm=max(tr[lc].rm+tr[rc].s+tr[x].d,tr[rc].rm);}int a[110000];int bt(int l,int r){ ???if(l>r) return 0; ???int now=++len;int mid=(l+r)/2; ???tr[now].d=a[mid]; ???tr[now].fz=tr[now].zf=false; ???tr[now].son[0]=bt(l,mid-1);tr[now].son[1]=bt(mid+1,r); ???int lc=tr[now].son[0],rc=tr[now].son[1]; ???if(lc!=0) tr[lc].f=now; ???if(rc!=0) tr[rc].f=now; ???update(now); ???return now;}void rotate(int x,int w){ ???int f=tr[x].f,ff=tr[f].f; ???int r,R; ???r=tr[x].son[w];R=f; ???tr[R].son[1-w]=r; ???if(r!=0) tr[r].f=R; ???r=x;R=ff; ???if(tr[R].son[0]==f) tr[R].son[0]=r; ???else tr[R].son[1]=r; ???tr[r].f=R; ???r=f;R=x; ???tr[R].son[w]=r; ???tr[r].f=R; ???update(f); ???update(x);}int tmp[110000],s;void splay(int x,int rt){ ???int i=x;s=0; ???while(tr[i].f!=rt) ???{ ???????tmp[++s]=i; ???????i=tr[i].f; ???} ???tmp[++s]=i; ???while(s!=0) ???{ ???????i=tmp[s--]; ???????if(tr[i].fz==true) fanzhuan(i); ???????if(tr[i].zf==true) zhuanfan(i); ???} ???while(tr[x].f!=rt) ???{ ???????int f=tr[x].f,ff=tr[f].f; ???????if(ff==rt) ???????{ ???????????if(tr[f].son[0]==x) rotate(x,1); ???????????else rotate(x,0); ???????} ???????else ???????{ ???????????if(tr[f].son[0]==x&&tr[ff].son[0]==f){rotate(f,1);rotate(x,1);continue;} ???????????if(tr[f].son[1]==x&&tr[ff].son[0]==f){rotate(x,0);rotate(x,1);continue;} ???????????if(tr[f].son[0]==x&&tr[ff].son[1]==f){rotate(x,1);rotate(x,0);continue;} ???????????if(tr[f].son[1]==x&&tr[ff].son[1]==f){rotate(f,0);rotate(x,0);continue;} ???????} ???} ???if(rt==0) root=x;}int finddizhi(int k){ ???int x=root; ???while(1) ???{ ???????if(tr[x].fz==true) fanzhuan(x); ???????if(tr[x].zf==true) zhuanfan(x); ???????int lc=tr[x].son[0],rc=tr[x].son[1]; ???????if(k<=tr[lc].c) x=lc; ???????else if(k>tr[lc].c+1){k-=tr[lc].c+1;x=rc;} ???????else break; ???} ???return x;}void findmin(int l,int r){ ???int lc=finddizhi(l-1),rc=finddizhi(r+1); ???splay(lc,0);splay(rc,lc); ???int x=tr[rc].son[0]; ???printf("%d\n",(abs(tr[x].ln)+1)/2+(tr[x].rm+1)/2);}void zhuanfan_(int l,int r){ ???int lc=finddizhi(l-1); ???int rc=finddizhi(r+1); ???splay(lc,0);splay(rc,lc); ???int x=tr[rc].son[0]; ???tr[x].ln=-tr[x].ln;tr[x].lm=-tr[x].lm; ???swap(tr[x].ln,tr[x].lm); ???tr[x].rn=-tr[x].rn;tr[x].rm=-tr[x].rm; ???swap(tr[x].rn,tr[x].rm); ???tr[x].s=-tr[x].s;tr[x].d=-tr[x].d; ???tr[x].zf^=1; ???splay(x,0);}void fanzhuan_(int l,int r){ ???int lc=finddizhi(l-1),rc=finddizhi(r+1); ???splay(lc,0);splay(rc,lc); ???int x=tr[rc].son[0]; ???swap(tr[x].ln,tr[x].rn); ???swap(tr[x].lm,tr[x].rm); ???tr[x].fz^=1; ???splay(x,0);}char st[110000];int main(){ ???int n,q; ???scanf("%d%d",&n,&q); ???scanf("%s",st+1); ???for(int i=1;i<=n;i++) ???{ ???????if(st[i]==‘(‘) a[i+1]=1; ???????else a[i+1]=-1; ???} ???len=0;root=bt(1,n+2); ???for(int i=1;i<=q;i++) ???{ ???????int t,l,r; ???????scanf("%d%d%d",&t,&l,&r);l++;r++; ???????if(t==0) findmin(l,r); ???????if(t==1) zhuanfan_(l,r); ???????if(t==2) fanzhuan_(l,r); ???} ???return 0;}BZOJ2209: [Jsoi2011]括号序列
原文地址：https://www.cnblogs.com/Never-mind/p/8947406.html