BZOJ2209: [Jsoi2011]括號序列

Description

Input

輸入數據的第一行包含兩個整數N和Q，分別表示括號序列的長度，以及操作的個數。 第二行包含一個長度為N的括號序列。 接下來Q行，每行三個整數t、x和y，分別表示操作的類型、操作的開始位置和操作的結 束位置，輸入數據保證x不小于y。其中t=0表示詢問操作、t=1表示反轉操作、t=2表示翻轉操 作。

Output

對于每一個詢問操作，輸出一行，表示將括號序列的該子序列修改為配對，所需的最少改動 個數。

Sample Input

6 3
)(())(
0 1 6
0 1 4
0 3 4

Sample Output

2
2
0

HINT

100%的數據滿足N,Q不超過10^5。

---

題解Here! 貌似重題了吧。。。

?

題目在此：BZOJ2329: [HNOI2011]括號修復 刪刪改改就好辣！ 附代碼： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 100010 using namespace std; int n,m,size=0,root; int val[MAXN]; char ch[MAXN]; struct Splay{int f,s,rev,inv,son[2];int v,sum,maxl,minl,maxr,minr;//v: 1 -> ( -1 -> ) }a[MAXN]; inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w; } inline int min(const int x,const int y){return x<y?x:y;} inline int max(const int x,const int y){return x>y?x:y;} inline void pushup(int rt){if(!rt)return;a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+1;a[rt].sum=a[a[rt].son[0]].sum+a[a[rt].son[1]].sum+a[rt].v;a[rt].maxl=max(a[a[rt].son[0]].maxl,a[a[rt].son[0]].sum+a[rt].v+a[a[rt].son[1]].maxl);a[rt].minl=min(a[a[rt].son[0]].minl,a[a[rt].son[0]].sum+a[rt].v+a[a[rt].son[1]].minl);a[rt].maxr=max(a[a[rt].son[1]].maxr,a[a[rt].son[1]].sum+a[rt].v+a[a[rt].son[0]].maxr);a[rt].minr=min(a[a[rt].son[1]].minr,a[a[rt].son[1]].sum+a[rt].v+a[a[rt].son[0]].minr); } inline void pushdown_rev(int rt){if(!rt)return;a[rt].rev^=1;swap(a[rt].son[0],a[rt].son[1]);swap(a[rt].maxl,a[rt].maxr);swap(a[rt].minl,a[rt].minr); } inline void pushdown_inv(int rt){if(!rt)return;a[rt].inv^=1;a[rt].v=-a[rt].v;a[rt].sum=-a[rt].sum;a[rt].maxl=-a[rt].maxl;a[rt].minl=-a[rt].minl;a[rt].maxr=-a[rt].maxr;a[rt].minr=-a[rt].minr;swap(a[rt].maxl,a[rt].minl);swap(a[rt].maxr,a[rt].minr); } inline void pushdown(int rt){if(!rt)return;if(a[rt].rev){pushdown_rev(a[rt].son[0]);pushdown_rev(a[rt].son[1]);a[rt].rev=0;}if(a[rt].inv){pushdown_inv(a[rt].son[0]);pushdown_inv(a[rt].son[1]);a[rt].inv=0;} } inline void turn(int rt,int k){int x=a[rt].f,y=a[x].f;pushdown(x);pushdown(rt);a[x].son[k^1]=a[rt].son[k];if(a[rt].son[k])a[a[rt].son[k]].f=x;a[rt].f=y;if(y)a[y].son[a[y].son[1]==x]=rt;a[x].f=rt;a[rt].son[k]=x;pushup(x);pushup(rt); } void splay(int rt,int ancestry){while(a[rt].f!=ancestry){int x=a[rt].f,y=a[x].f;if(y==ancestry)turn(rt,a[x].son[0]==rt);else{int k=a[y].son[0]==x?1:0;if(a[x].son[k]==rt){turn(rt,k^1);turn(rt,k);}else{turn(x,k);turn(rt,k);}}}if(ancestry==0)root=rt; } inline int newnode(int x){int rt=++size;a[rt].son[0]=a[rt].son[1]=a[rt].f=0;a[rt].rev=a[rt].inv=0;a[rt].s=1;a[rt].v=a[rt].sum=val[x];return rt; } int buildtree(int l,int r){if(l>r)return 0;int lson=0,rson=0,mid=l+r>>1;lson=buildtree(l,mid-1);int rt=newnode(mid);rson=buildtree(mid+1,r);a[rt].son[0]=lson;a[rt].son[1]=rson;if(lson)a[lson].f=rt;if(rson)a[rson].f=rt;pushup(rt);return rt; } int kth(int rt,int k){while(1){pushdown(rt);int y=a[rt].son[0];if(k>a[y].s+1){k-=a[y].s+1;rt=a[rt].son[1];}else if(k<=a[y].s)rt=y;else return rt;} } inline void reverse(int l,int r){int front=kth(root,l),next=kth(root,r+2),q;splay(front,0);splay(next,front);q=a[next].son[0];pushdown_rev(q);pushup(next);pushup(front); } inline void invert(int l,int r){int front=kth(root,l),next=kth(root,r+2),q;splay(front,0);splay(next,front);q=a[next].son[0];pushdown_inv(q);pushup(next);pushup(front); } inline void query(int l,int r){int front=kth(root,l),next=kth(root,r+2),q;splay(front,0);splay(next,front);q=a[next].son[0];int ans=((a[q].maxr+1)>>1)-(a[q].minl-1)/2;printf("%d\n",ans); } void work(){char k[2];int f,x,y;while(m--){f=read();x=read();y=read();if(f==0)query(x,y);else if(f==1)invert(x,y);else reverse(x,y);} } void init(){n=read();m=read();scanf("%s",ch+2);for(int i=2;i<=n+1;i++)val[i]=(ch[i]==')'?-1:1);val[1]=val[n+2]=0;root=buildtree(1,n+2); } int main(){init();work();return 0; }

?

轉載于:https://www.cnblogs.com/Yangrui-Blog/p/9612530.html

總結

以上是生活随笔為你收集整理的BZOJ2209: [Jsoi2011]括号序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。