【SPOJ61】Brackets（线段树）

题意：给出一个括号序列，要求维护两种操作：

1.将第x位上的括号取反

2.查询当前整个括号序列是否匹配

n<=3e4

思路：线段树维护区间内没有匹配的左右括号数量

pushup时t[p].r=t[rs].r+t[ls].r-min(t[ls].l,t[rs].r)

不知道这个式子怎么推出来的，但在四种情况下它都成立

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<map>
  8 #include<set>
  9 #include<queue>
 10 #include<vector>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef unsigned int uint;
 14 typedef unsigned long long ull;
 15 typedef pair<int,int> PII;
 16 typedef vector<int> VI;
 17 #define fi first
 18 #define se second
 19 #define MP make_pair
 20 #define N   210000
 21 #define M   7010
 22 #define eps 1e-8
 23 #define pi  acos(-1)
 24 #define oo  1e9
 25 #define MOD 10007
 26 
 27 struct node
 28 {
 29     int l,r;
 30 }t[N];
 31 char a[N];
 32 int n;
 33 
 34 
 35 void pushup(int p)
 36 {
 37     int ls=p<<1; 
 38     int rs=ls+1;
 39     t[p].l=t[ls].l+t[rs].l-min(t[ls].l,t[rs].r);
 40     t[p].r=t[rs].r+t[ls].r-min(t[ls].l,t[rs].r);
 41 }
 42 
 43 void build(int l,int r,int p)
 44 {
 45     t[p].l=t[p].r=0;
 46     if(l==r)
 47     {
 48         if(a[l]=='(') t[p].l=1;
 49          else t[p].r=1;
 50         return;
 51     }
 52     int mid=(l+r)>>1;
 53     build(l,mid,p<<1);
 54     build(mid+1,r,p<<1|1);
 55     pushup(p);
 56 }
 57 
 58 void update(int l,int r,int x,int p)
 59 {
 60     if(l==r)
 61     {
 62         t[p].l=1-t[p].l;
 63         t[p].r=1-t[p].r;
 64         return;
 65     }
 66     int mid=(l+r)>>1;
 67     if(x<=mid) update(l,mid,x,p<<1);
 68      else update(mid+1,r,x,p<<1|1);
 69     pushup(p);
 70 }
 71 
 72 int main()
 73 {
 74     //freopen("spoj61.in","r",stdin);
 75     //freopen("spoj61.out","w",stdout); 
 76     int cas=0;
 77     while(scanf("%d",&n)!=EOF)
 78     {
 79         cas++;
 80         printf("Test %d:
",cas);
 81         scanf("%s",a+1);
 82         int m;
 83         scanf("%d",&m);
 84         build(1,n,1); 
 85         for(int i=1;i<=m;i++)
 86         {
 87             int x;
 88             scanf("%d",&x);
 89             if(x==0) 
 90             {
 91                 if(t[1].l==0&&t[1].r==0) printf("YES
");
 92                  else printf("NO
");
 93             }
 94              else update(1,n,x,1);
 95         }
 96     }
 97     return 0;
 98 }
 99     
100