2329: [HNOI2011]括号修复
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 485 Solved: 240
[Submit][Status]
Description
Input
Output
Sample Input
Sample Output
HINT
Source
题解：
注意到把相互抵消的去掉，区间一定形如）））（（（，ans就是 各自的个数+1除以2在加起来。
然后我们考虑如何维护左边括号的个数。
考虑把）看作-1，（看作1，然后lmin和rmax就是我们所需要的，就可以类似最大连续和搞了。
然后是标记下传的问题。我是这样处理的（显然inv和rev的顺序无所谓）：
1）cov一次，inv和rev全部清零。
2）inv的时候，更新了信息，如果已被cov，则inv[x]清零
3）rev的时候，如果已被cov则不更新任何信息
然后pushdown的时候直接处理即可，先后顺序就无关了。
代码：
View Code
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 150000+5 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26 int x=0,f=1;char ch=getchar(); 27 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 28 while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();} 29 return x*f; 30 } 31 int n,m,c[maxn][2],fa[maxn],li[maxn],ri[maxn],lx[maxn],rx[maxn],sum[maxn],s[maxn],v[maxn]; 32 int rt,t1,t2; 33 bool cov[maxn],rev[maxn],inv[maxn]; 34 inline void pushup(int x) 35 { 36 int l=c[x][0],r=c[x][1]; 37 s[x]=s[l]+s[r]+1; 38 sum[x]=sum[l]+sum[r]+v[x]; 39 lx[x]=max(lx[l],sum[l]+v[x]+max(0,max(lx[r],sum[r]))); 40 rx[x]=max(rx[r],sum[r]+v[x]+max(0,max(rx[l],sum[l]))); 41 li[x]=min(li[l],sum[l]+v[x]+min(0,min(li[r],sum[r]))); 42 ri[x]=min(ri[r],sum[r]+v[x]+min(0,min(ri[l],sum[l]))); 43 } 44 inline void rotate(int x,int &k) 45 { 46 int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 47 if(y!=k)c[z][c[z][1]==y]=x;else k=x; 48 fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 49 c[y][l]=c[x][r];c[x][r]=y; 50 pushup(y);pushup(x); 51 } 52 inline void splay(int x,int &k) 53 { 54 while(x!=k) 55 { 56 int y=fa[x],z=fa[y]; 57 if(y!=k) 58 { 59 if(c[z][0]==y^c[y][0]==x)rotate(x,k);else rotate(y,k); 60 } 61 rotate(x,k); 62 } 63 } 64 inline void cover(int x,int y) 65 { 66 cov[x]=1;v[x]=y;rev[x]=inv[x]=0; 67 sum[x]=s[x]*y; 68 lx[x]=rx[x]=y>0?sum[x]:0; 69 li[x]=ri[x]=y>0?0:sum[x]; 70 } 71 inline void rever(int x) 72 { 73 if(cov[x])return; 74 rev[x]^=1; 75 swap(c[x][0],c[x][1]); 76 swap(lx[x],rx[x]); 77 swap(li[x],ri[x]); 78 } 79 inline void invert(int x) 80 { 81 inv[x]^=1;v[x]=-v[x]; 82 swap(li[x],lx[x]);li[x]=-li[x];lx[x]=-lx[x]; 83 swap(ri[x],rx[x]);ri[x]=-ri[x];rx[x]=-rx[x]; 84 sum[x]=-sum[x]; 85 if(cov[x])inv[x]=0; 86 } 87 inline void pushdown(int x) 88 { 89 if(cov[x]){cover(c[x][0],v[x]);cover(c[x][1],v[x]);cov[x]=0;} 90 if(rev[x]){rever(c[x][0]);rever(c[x][1]);rev[x]=0;} 91 if(inv[x]){invert(c[x][0]);invert(c[x][1]);inv[x]=0;} 92 } 93 inline int find(int x,int k) 94 { 95 pushdown(x); 96 int l=c[x][0],r=c[x][1]; 97 if(s[l]+1==k)return x; 98 else if(s[l]>=k)return find(l,k); 99 else return find(r,k-s[l]-1); 100 } 101 inline void split(int l,int r) 102 { 103 t1=find(rt,l);t2=find(rt,r); 104 splay(t1,rt);splay(t2,c[t1][1]); 105 } 106 inline void build(int l,int r,int f) 107 { 108 if(l>r)return; 109 int x=(l+r)>>1; 110 fa[x]=f;c[f][x>f]=x; 111 if(l==r){s[x]=1;li[x]=ri[x]=v[x]>0?0:v[x];lx[x]=rx[x]=v[x]>0?v[x]:0;sum[x]=v[x];return;} 112 build(l,x-1,x);build(x+1,r,x); 113 pushup(x); 114 } 115 int main() 116 { 117 freopen("input.txt","r",stdin); 118 freopen("output.txt","w",stdout); 119 n=read();m=read(); 120 v[1]=v[n+2]=0; 121 for2(i,2,n+1){char ch=getchar();while(ch!='('&&ch!=')')ch=getchar();v[i]=ch=='('?1:-1;} 122 build(1,n+2,0);rt=(1+n+2)>>1; 123 while(m--) 124 { 125 int ch=read();int x=read(),y=read();split(x,y+2);int z=c[t2][0]; 126 if(!ch)printf("%d ",(-li[z]+1)/2+(rx[z]+1)/2); 127 else if(ch==1)invert(z);else rever(z); 128 pushup(t2);pushup(t1); 129 } 130 return 0; 131 }