首页 > 代码库 > BZOJ 2209: [Jsoi2011]括号序列 [splay 括号]

BZOJ 2209: [Jsoi2011]括号序列 [splay 括号]

2209: [Jsoi2011]括号序列

Time Limit: 20 Sec  Memory Limit: 259 MB
Submit: 1111  Solved: 541
[Submit][Status][Discuss]

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

Source

第一轮


 

背景:把钥匙锁机房里了只能来电子阅览室,在寒冷潮湿的空气中竟然1A了太感动了(虽然不完全是自己想出来的)

 

括号问题一个常用手法是 ( -1  ) +1

最后要修改的一定是)))((((这个样子,而)))的个数就是这个序列的最小前缀和,(((同理

那么修改次数就是(lmn+1)/2+(rmx+1)/2

信息合并和动态最大子序列问题很像啦

翻转和反转之后信息如何维护?

翻转:只要交换l..和r..就好了

反转:所有.mx .mn都要取负,然后swap(lmx,lmn) swap(rmx,rmn)

 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;#define lc t[x].ch[0]#define rc t[x].ch[1]#define pa t[x].faconst int N=1e5+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1; c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0; c=getchar();}    return x*f;}int n,Q,l,r,a[N];char s[N],op[20];struct node{    int ch[2],fa,size,v,sum,lmx,lmn,rmx,rmn,rev,flp;    node():fa(0){ch[0]=ch[1]=0;}}t[N];int root;inline int wh(int x){return t[pa].ch[1]==x;}inline void update(int x){    if(!x) return;    t[x].size=t[lc].size+t[rc].size+1;    t[x].sum=t[lc].sum+t[rc].sum+t[x].v;    t[x].lmx=max(t[lc].lmx,max(t[lc].sum+t[x].v,t[lc].sum+t[x].v+t[rc].lmx));    t[x].lmn=min(t[lc].lmn,min(t[lc].sum+t[x].v,t[lc].sum+t[x].v+t[rc].lmn));    t[x].rmx=max(t[rc].rmx,max(t[rc].sum+t[x].v,t[rc].sum+t[x].v+t[lc].rmx));    t[x].rmn=min(t[rc].rmn,min(t[rc].sum+t[x].v,t[rc].sum+t[x].v+t[lc].rmn));    }inline void rever(int x){    t[x].rev^=1;    swap(lc,rc);    swap(t[x].lmx,t[x].rmx);    swap(t[x].lmn,t[x].rmn);}inline void flip(int x){    t[x].flp^=1;    t[x].sum=-t[x].sum;t[x].v=-t[x].v;    t[x].lmx=-t[x].lmx;t[x].lmn=-t[x].lmn;    swap(t[x].lmx,t[x].lmn);    t[x].rmx=-t[x].rmx;t[x].rmn=-t[x].rmn;    swap(t[x].rmx,t[x].rmn);}inline void pushDown(int x){    if(t[x].rev){        if(lc) rever(lc);        if(rc) rever(rc);        t[x].rev=0;    }    if(t[x].flp){        if(lc) flip(lc);        if(rc) flip(rc);        t[x].flp=0;    }}inline void rotate(int x){    int f=t[x].fa,g=t[f].fa,c=wh(x);    if(g) t[g].ch[wh(f)]=x;t[x].fa=g;    t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f;    t[x].ch[c^1]=f;t[f].fa=x;    update(f);update(x);}inline void splay(int x,int tar){    for(;pa!=tar;rotate(x))        if(t[pa].fa!=tar) rotate(wh(x)==wh(pa)?pa:x);    if(tar==0) root=x;}int build(int l,int r,int f){//printf("build %d %d %d\n",l,r,f);    if(l>r) return 0;    int x=(l+r)>>1;    lc=build(l,x-1,x);rc=build(x+1,r,x);    t[x].fa=f;    t[x].rev=t[x].flp=0;//printf("al %d\n",a[l]);    t[x].v=a[x];//not need    update(x);//printf("get %d %d %d  %d %d  %d %d %d %d\n",x,l,r,t[x].v,t[x].sum,t[x].lmx,t[x].lmn,t[x].rmx,t[x].rmn);    return x;}inline int kth(int k){//printf("kth %d\n",k);    int x=root,ls=0;    while(x){        pushDown(x);        int _=ls+t[lc].size;//printf("size %d %d\n",x,_);        if(_<k&&k<=_+1) return x;        else if(k<=_) x=lc;        else ls=_+1,x=rc;    }    return 0;}void Query(int l,int r){//printf("query %d %d\n",l,r);    int f=kth(l);splay(f,0);    int x=kth(r+2);splay(x,f);    int a=t[lc].lmx,b=t[lc].rmn;//printf("hi %d %d %d  %d %d\n",f,x,lc,a,b);    printf("%d\n",(a+1)/2+(-b+1)/2);}void Flip(int l,int r){    int f=kth(l);splay(f,0);    int x=kth(r+2);splay(x,f);    flip(lc);update(x);update(f);}void Rever(int l,int r){    int f=kth(l);splay(f,0);    int x=kth(r+2);splay(x,f);    rever(lc);update(x);update(f);}int main(){    //freopen("in.txt","r",stdin);    n=read();Q=read();    scanf("%s",s+1);    for(int i=1;i<=n;i++) a[i+1]=s[i]==(?-1:1;    //for(int i=1;i<=n+2;i++) printf("%d ",a[i]);puts("");    t[0].lmn=t[0].rmn=INF;    t[0].lmx=t[0].rmx=-INF;    root=build(1,n+2,root);    while(Q--){        scanf("%s",op);l=read();r=read();        if(op==0) Query(l,r);        if(op==1) Flip(l,r);        if(op==2) Rever(l,r);    }}

 

 

BZOJ 2209: [Jsoi2011]括号序列 [splay 括号]