当前位置：首页 > news >正文

SPOJ-BRCKTS （括号序列，线段树）

news 来源：原创 2024/5/20 23:00:03

维护括号序列 Replace(i):

将第i个位置的括号反向。

Check：测试当前序列是否合法。

题解

　　　　将左括号定为1，右括号定为-1，所以只需要满足前缀和序列没有负数即可，即最小值

　　　　为正即可，第i个括号反向，就是该位置----n减2或者加2

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdio>
 6 
 7 #define N 30007
 8 using namespace std;
 9 
10 int n,q;
11 char s[N];
12 int a[N],tr[N*4],flag[N*4];
13 
14 void update(int p)
15 {
16     tr[p]=min(tr[p<<1],tr[p<<1|1]);
17 }
18 void downdate(int p)
19 {
20     if (flag[p]==0) return;
21     tr[p<<1]+=flag[p],tr[p<<1|1]+=flag[p];
22     flag[p<<1]+=flag[p],flag[p<<1|1]+=flag[p];
23     flag[p]=0;
24 }
25 void build(int p,int l,int r)
26 {
27     if (l==r)
28     {
29         tr[p]=a[l];flag[p]=0;
30         return;
31     }
32     
33     int mid=(l+r)>>1;
34     build(p<<1,l,mid),build(p<<1|1,mid+1,r);
35     update(p);flag[p]=0;
36 }
37 void change(int p,int l,int r,int x,int y,int z)
38 {
39     if (l==x&&r==y)
40     {
41         tr[p]=tr[p]+z;
42         flag[p]+=z;
43         return;
44     }
45     downdate(p);
46     int mid=(l+r)>>1;
47     if (y<=mid) change(p<<1,l,mid,x,y,z);
48     else if (x>mid) change(p<<1|1,mid+1,r,x,y,z);
49     else change(p<<1,l,mid,x,mid,z),
50         change(p<<1|1,mid+1,r,mid+1,y,z);
51     update(p);
52 }
53 int query(int p,int l,int r,int x,int y)
54 {
55     if (l==x&&r==y) return tr[p];
56     downdate(p);
57     int mid=(l+r)>>1;
58     if (y<=mid) return query(p<<1,l,mid,x,y);
59     else if (x>mid) return query(p<<1|1,mid+1,r,x,y);
60     else return min(query(p<<1,l,mid,x,mid),query(p<<1|1,mid+1,r,mid+1,r));
61     update(p);
62 }
63 int main()
64 {
65     int CASE=0;
66     while (~scanf("%d",&n))
67     {
68         printf("Test %d:\n",++CASE);
69         scanf("%s",s+1);
70         for(int i=1;i<=n;i++)
71             if (s[i]=='(') a[i]=1;
72             else a[i]=-1;
73         for (int i=1;i<=n;i++) a[i]=a[i-1]+a[i];    
74         build(1,1,n);
75         scanf("%d",&q);
76         for (int i=1;i<=q;i++)
77         {
78             int x;scanf("%d",&x);
79             if (x==0)
80             {
81                 if (query(1,1,n,n,n)==0&&tr[1]==0) printf("YES\n");
82                 else printf("NO\n");
83             }
84             else
85             {
86                 change(1,1,n,x,n,(s[x]=='(')?-2:2);
87                 if (s[x]=='(')s[x]=')';
88                 else s[x]='(';
89             }
90         }
91     }
92 }