首页 > 代码库 > BZOJ2329 HNOI2011 括号修复 平衡树
BZOJ2329 HNOI2011 括号修复 平衡树
题意：给定一个由（，）组成的括号序列，维护：1、将[a,b]修改为同一种半括号 2、将[a,b]翻转 3、将[a,b]的（变为），）变为（ 4、求[a,b]最少要添加多少个括号才能合法
题解：
不算太裸的平衡树……论标记的正确打法。
对于一个括号序列，我们总能简化成一个左边全是右括号，右边全是左括号的序列，像酱紫：）））））（（（（（。当然有可能是没有左括号或者右括号的
我们定义）==-1，（==1。然后我们用打标记的方法来维护从左起的最小序列和lmin和从右起的最大序列和rmax，显然这两个的值分别是简化后右括号和左括号的数量，那么答案就是(-lmin+1)/2+(rmax+1)/2
我们建树来维护lmin,lmax,rmin,rmax，翻转、改变、取反操作全部用打标记的方法，至于怎么打可以参考线段树的lazy标记，其中取反操作就是交换min和max。
有一个细节上的问题：如果改变操作在取反操作之后进行，就要删除取反标记，因为之前不论你怎么取反，一改变就统统作废了。下方标记时亦是如此。
最后就是代码实现了……
#include <cstdio>#include <climits>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXN=100000+2;typedef struct NODE{ int c,s,v,lmin,rmin,lmax,rmax; bool same,rev,inv; NODE *child[2],*f; NODE(int _v,NODE *_f):s(_v),v(_v),f(_f){}} *TREE;TREE root,Null;int N,M,a[MAXN];char s[MAXN];TREE NewNode(int v,TREE f){ TREE x=new NODE(v,f); x->c=1; x->lmax=x->rmax=max(v,0); x->lmin=x->rmin=min(v,0); x->same=x->rev=x->inv=0; x->child[0]=x->child[1]=Null; return x;}void Initialization(){ Null=NewNode(0,0),Null->c=0; root=NewNode(0,Null); root->child[1]=NewNode(0,root); Null->s=root->s=root->child[1]->s=0;}void Pushup(TREE x){ if(x==Null) return; x->c=x->child[0]->c+x->child[1]->c+1; x->s=x->child[0]->s+x->child[1]->s+x->v; x->lmin=min(x->child[0]->lmin,x->child[0]->s+x->v+min(0,x->child[1]->lmin)); x->rmin=min(x->child[1]->rmin,x->child[1]->s+x->v+min(0,x->child[0]->rmin)); x->lmax=max(x->child[0]->lmax,x->child[0]->s+x->v+max(0,x->child[1]->lmax)); x->rmax=max(x->child[1]->rmax,x->child[1]->s+x->v+max(0,x->child[0]->rmax));}void Pushdown(TREE x){ if(x==Null) return; if(x->rev){ swap(x->child[0],x->child[1]),swap(x->lmin,x->rmin),swap(x->lmax,x->rmax); x->child[0]->rev^=1,x->child[1]->rev^=1,x->rev=0; } if(x->same){ x->s=x->v*x->c; x->lmax=x->rmax=max(0,max(x->v,x->s)); x->lmin=x->rmin=min(0,min(x->v,x->s)); x->child[0]->same=1,x->child[0]->v=x->v,x->child[0]->inv=0;//删除取反标记 x->child[1]->same=1,x->child[1]->v=x->v,x->child[1]->inv=0;//删除取反标记 x->same=0; } if(x->inv){ x->v=-x->v,x->s=-x->s; swap(x->lmin,x->lmax),swap(x->rmin,x->rmax); x->lmin*=-1,x->rmin*=-1,x->lmax*=-1,x->rmax*=-1; x->child[0]->inv^=1,x->child[1]->inv^=1,x->inv=0; }}void Rotate(TREE x,bool t){ TREE y=x->f; Pushdown(x->child[0]),Pushdown(x->child[1]),Pushdown(y->child[t]); y->child[!t]=x->child[t],x->child[t]->f=y,x->f=y->f; if(y->f->child[0]==y) y->f->child[0]=x; else y->f->child[1]=x; y->f=x,x->child[t]=y; Pushup(y),Pushup(x); if(y==root) root=x;}void Splay(TREE x,TREE y){ Pushdown(x); while(x->f!=y) if(x->f->f==y) if(x->f->child[0]==x) Rotate(x,1); else Rotate(x,0); else if(x->f->f->child[0]==x->f) if(x->f->child[0]==x) Rotate(x->f,1),Rotate(x,1); else Rotate(x,0),Rotate(x,1); else if(x->f->child[0]==x) Rotate(x,1),Rotate(x,0); else Rotate(x->f,0),Rotate(x,0);}void Select(int p,TREE y){ TREE x=root;Pushdown(x); while(p!=x->child[0]->c+1){ if(p<=x->child[0]->c) x=x->child[0]; else p-=x->child[0]->c+1,x=x->child[1]; Pushdown(x); } Splay(x,y);}void Insert(int p,int n,int *a){ TREE s,t; s=t=NewNode(a[1],Null); for(int i=2;i<=n;i++) t=t->child[1]=NewNode(a[i],t); Select(p+1,Null),Select(p+2,root); root->child[1]->child[0]=s,s->f=root->child[1]; Splay(t,Null);}void Change(int p,int n,int v){ Select(p,Null),Select(p+n+1,root); root->child[1]->child[0]->same=1,root->child[1]->child[0]->v=v; root->child[1]->child[0]->inv=0;//删除取反标记 Splay(root->child[1]->child[0],Null);}void Reverse(int p,int n){ Select(p,Null),Select(p+n+1,root); root->child[1]->child[0]->rev^=1; Splay(root->child[1]->child[0],Null);}void Invert(int p,int n){ Select(p,Null),Select(p+n+1,root); root->child[1]->child[0]->inv^=1; Splay(root->child[1]->child[0],Null);}int Query(int p,int n){ Select(p,Null),Select(p+n+1,root); Pushdown(root->child[1]->child[0]); int x=(-root->child[1]->child[0]->lmin+1)>>1; int y=(root->child[1]->child[0]->rmax+1)>>1; return x+y;}int main(){ Initialization(); cin >> N >> M; cin >> s; for(int i=1;i<=N;i++) if(s[i-1]==‘(‘) a[i]=1; else a[i]=-1; Insert(0,N,a); for(int i=1,a,b;i<=M;i++){ cin >> s; cin >> a >> b; if(strstr(s,"Replace")){ cin >> s; if(s[0]==‘(‘) Change(a,b-a+1,1); else Change(a,b-a+1,-1); } if(strstr(s,"Swap")) Reverse(a,b-a+1); if(strstr(s,"Invert")) Invert(a,b-a+1); if(strstr(s,"Query")) cout << Query(a,b-a+1) << endl; } return 0;}
BZOJ2329 HNOI2011 括号修复 平衡树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。