BZOJ2329HNOI2011括号修复Splay

ああああああああああああああ——散弾铳とテレキャスター　言叶の整列、アンハッピー  単身、都会の町并み　撃ち込んだ音、嫌いですか&＃xff1f; 

题目大意&＃xff1a;给定一个括号序列&＃xff0c;提供四种操作&＃xff1a;

1.将一段区间内的所有括号的变成&＃39;(&＃39;或者&＃39;)&＃39;

2.将一段区间反转

3.将一段区间内的所有括号翻转&＃xff0c;即&＃39;(&＃39;变成‘)&＃39;&＃xff0c;&＃39;)&＃39;变成&＃39;(&＃39;

4.查询一段区间内要将至少多少个括号翻转才能变成一个合法的括号序列

5.没有5了我打多了

我依稀记得我刚开始打这道题的时候那还是一个阳光明媚的中午。。。中午。。。中午

题目略恶心 我们简单分析一下

比如说对于一个括号序列))(((())((

我们把所有匹配成功的括号全都删掉&＃xff0c;得到一个简化版的括号序列&＃xff1a;

))((((

不难发现左面都是&＃39;(&＃39;右面都是&＃39;)&＃39;

然后这个东西怎么维护呢&＃xff1f;

我们令&＃39;(&＃39;&＃61;1,&＃39;)&＃39;&＃61;-1

那么。。。

不打了&＃xff01;&＃xff01;&＃xff01;麻烦死了&＃xff01;&＃xff01;&＃xff01;题解 http://www.cnblogs.com/oldmanren/archive/2011/11/24/2262178.html

这里只简单介绍标记的处理方式

首先当我们获得一个修改标记的时候&＃xff0c;括号翻转标记和区间反转标记都要清零&＃xff0c;因为这段区间已经被重新覆盖了&＃xff0c;没必要再括号翻转和区间反转了

于是当修改标记和另两个标记共存时&＃xff0c;一定是修改标记先获得&＃xff0c;所以我们先下传修改标记

然后另两个标记互不干扰 随便选一个顺序下传就可以了。

最后代码

#include
#include
#include
#include
#include
#define M 100100
using namespace std;
struct bracket_sequence{int sum;int lmax,rmax;int lmin,rmin;void flip(){sum*&＃61;-1;swap(lmax,lmin);swap(rmax,rmin);lmax*&＃61;-1;lmin*&＃61;-1;rmax*&＃61;-1;rmin*&＃61;-1;}void reverse(){swap(lmax,rmax);swap(lmin,rmin);}bracket_sequence(int x,int siz){sum&＃61;x*siz;if(x&＃61;&＃61;1)lmax&＃61;rmax&＃61;sum,lmin&＃61;rmin&＃61;0;elselmin&＃61;rmin&＃61;sum,lmax&＃61;rmax&＃61;0;}
};
bracket_sequence operator &＃43; (const bracket_sequence x,const bracket_sequence y)
{bracket_sequence re(0,0);re.sum&＃61;x.sum&＃43;y.sum;re.lmax&＃61;max(x.lmax,x.sum&＃43;y.lmax);re.rmax&＃61;max(y.rmax,y.sum&＃43;x.rmax);re.lmin&＃61;min(x.lmin,x.sum&＃43;y.lmin);re.rmin&＃61;min(y.rmin,y.sum&＃43;x.rmin);return re;
}
struct abcd{abcd *fa,*ls,*rs;int siz,num;bracket_sequence *bs;int flip_mark,rev_mark,change_mark;abcd(int x);void Push_Up();void Push_Down();
}*null&＃61;new abcd(0),*root&＃61;null;
abcd :: abcd(int x)
{siz&＃61;1;if(!x)siz&＃61;0;num&＃61;x;fa&＃61;ls&＃61;rs&＃61;null;bs&＃61;new bracket_sequence(x,siz);flip_mark&＃61;rev_mark&＃61;change_mark&＃61;0;
}
void abcd :: Push_Up()
{siz&＃61;ls->siz&＃43;rs->siz&＃43;1;*bs&＃61;(*ls->bs)&＃43;bracket_sequence(num,1)&＃43;(*rs->bs);
}
void abcd :: Push_Down()
{if(change_mark){ls->change_mark&＃61;ls->num&＃61;change_mark;rs->change_mark&＃61;rs->num&＃61;change_mark;*ls->bs&＃61;bracket_sequence(change_mark,ls->siz);*rs->bs&＃61;bracket_sequence(change_mark,rs->siz);ls->flip_mark&＃61;ls->rev_mark&＃61;0;rs->flip_mark&＃61;rs->rev_mark&＃61;0;change_mark&＃61;0;}if(flip_mark){ls->flip_mark^&＃61;1;rs->flip_mark^&＃61;1;ls->num*&＃61;-1;rs->num*&＃61;-1;ls->bs->flip();rs->bs->flip();flip_mark&＃61;0;}if(rev_mark){ls->rev_mark^&＃61;1;rs->rev_mark^&＃61;1;ls->bs->reverse();rs->bs->reverse();swap(ls->ls,ls->rs);swap(rs->ls,rs->rs);rev_mark&＃61;0;}
}
void Zig(abcd *x)
{abcd *y&＃61;x->fa;y->Push_Down();x->Push_Down();y->ls&＃61;x->rs;x->rs->fa&＃61;y;x->rs&＃61;y;x->fa&＃61;y->fa;if(y&＃61;&＃61;y->fa->ls)y->fa->ls&＃61;x;else if(y&＃61;&＃61;y->fa->rs)y->fa->rs&＃61;x;y->fa&＃61;x;y->Push_Up();if(root&＃61;&＃61;y)root&＃61;x;
}
void Zag(abcd *x)
{abcd *y&＃61;x->fa;y->Push_Down();x->Push_Down();y->rs&＃61;x->ls;x->ls->fa&＃61;y;x->ls&＃61;y;x->fa&＃61;y->fa;if(y&＃61;&＃61;y->fa->ls)y->fa->ls&＃61;x;else if(y&＃61;&＃61;y->fa->rs)y->fa->rs&＃61;x;y->fa&＃61;x;y->Push_Up();if(root&＃61;&＃61;y)root&＃61;x;
}
void Splay(abcd *x,abcd *Tar)
{while(1){abcd *y&＃61;x->fa,*z&＃61;y->fa;if(y&＃61;&＃61;Tar)break;if(z&＃61;&＃61;Tar){if(x&＃61;&＃61;y->ls) Zig(x);else Zag(x);break;}if(x&＃61;&＃61;y->ls){if(y&＃61;&＃61;z->ls)Zig(y);Zig(x);}else{if(y&＃61;&＃61;z->rs)Zag(y);Zag(x);}}x->Push_Up();
}
void Find(abcd *x,int y,abcd *z)
{while(1){x->Push_Down();if(y<&＃61;x->ls->siz)x&＃61;x->ls;else{y-&＃61;x->ls->siz;if(y&＃61;&＃61;1)break;y--;x&＃61;x->rs;}}Splay(x,z);
}
void Insert(abcd *&x,int y,abcd *z)
{if(x&＃61;&＃61;null){x&＃61;new abcd(y);x->fa&＃61;z;Splay(x,null);return ;}x->Push_Down();Insert(x->rs,y,x);
}
int n,m;
char s[M];
int main()
{int i,x,y;cin>>n>>m;scanf("%s",s&＃43;1);Insert(root,-2,null);for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)Insert(root,s[i]&＃61;&＃61;&＃39;(&＃39;?1:-1,null);Insert(root,2,null);for(i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%s%d%d",s,&x,&y);Find(root,x,null);Find(root,y&＃43;2,root);abcd *temp&＃61;root->rs->ls;if(s[0]&＃61;&＃61;&＃39;R&＃39;){scanf("%s",s);temp->change_mark&＃61;temp->num&＃61;(s[0]&＃61;&＃61;&＃39;(&＃39;?1:-1);*temp->bs&＃61;bracket_sequence(temp->change_mark,temp->siz);temp->flip_mark&＃61;temp->rev_mark&＃61;0;}else if(s[0]&＃61;&＃61;&＃39;S&＃39;){temp->rev_mark^&＃61;1;temp->bs->reverse();swap(temp->ls,temp->rs);}else if(s[0]&＃61;&＃61;&＃39;I&＃39;){temp->flip_mark^&＃61;1;temp->num*&＃61;-1;temp->bs->flip();}else{x&＃61;(int)ceil(abs(temp->bs->lmin)/2.0);y&＃61;(int)ceil(abs(temp->bs->rmax)/2.0);printf("%d\n", x&＃43;y );}}
}