Gym 100803G 线段树

好长时间前做的题，来补一下题解。

给出括号化的序列，每次改变一个括号方向，求出下标p，是的改变p处的括号方向可以使括号化仍然成立，且p最小。

保证括号化看似和线段树没有联系，我们可以把括号"("表示为1，把括号")"表示为-1，则保证括号化的充要条件就是使数字序列前缀和始终大于等于零

用线段树维护前缀和

查询有两种情况

1. "(" 变成 ")"

这种情况我们只需找到最左边的一个")"，就是答案。(可以用一个set维护所有的")"的位置)

2.")" 变成 "("

这种情况我们要找一个最左边的“（”变成”）“，也就是把p处及以后的前缀和都减2，且不能出现负的前缀和。

于是我们就要借助线段树查询前缀和小于2的最右边节点，这样把区间[p + 1, n]减二之后才不会出现负值。

用线段树维护区间最小值，也就是区间最小前缀和。线段树能往右走就往又走，注意查询过程中区间边界的特判处理。

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<set>
  5 #include<iostream>
  6 #define lson o << 1, L, M
  7 #define rson (o << 1) | 1, M + 1, R
  8 using namespace std;
  9 const int MAXN = 300010;
 10 const int INF = 0x3f3f3f3f;
 11 char str[MAXN];
 12 int num[MAXN];
 13 int minv[MAXN << 2];
 14 int addv[MAXN << 2];
 15 int len;
 16 void pushup(int o, int L, int R) {
 17     minv[o] = 0;
 18     if(R > L) {
 19         minv[o] = min(minv[o << 1], minv[(o << 1) | 1]);
 20     }
 21     minv[o] += addv[o];
 22 }
 23 void update(int p, int v, int o, int L, int R) {
 24     if(p == L && p == R) {
 25         addv[o] = v;
 26         minv[o] = 0;
 27     } else {
 28         int M = L + (R - L) / 2;
 29         if(p <= M) update(p, v, lson);
 30         else update(p, v, rson);
 31         
 32     }pushup(o, L, R);
 33 }
 34 void add(int l, int r, int v, int o, int L, int R) {
 35     if(l <= L && r >= R) {
 36         addv[o] += v;
 37     } else {
 38         int M = L + (R - L) / 2;
 39         if(l <= M)add(l, r, v, lson);
 40         if(r > M) add(l, r, v, rson);
 41     }
 42     pushup(o, L, R);
 43 }
 44 int query_min(int l ,int r, int add, int o, int L, int R) {
 45     if(l <= L && r >= R) {
 46         return minv[o] + add;
 47     } else {
 48         int M = L + (R - L) / 2;
 49         int res = INF;
 50         if(l <= M) res = min(res, query_min(l, r, add + addv[o],lson));
 51         if(r > M) res = min(res, query_min(l, r, add + addv[o], rson));
 52         return res;
 53     }
 54 }
 55 int query(int l, int r, int add, int o, int L, int R) { //cout << L << "!!!" << R << endl;
 56     if(L == R) {
 57         if(L == 1) {
 58             if(minv[o] + add >= 2) return 0;
 59             return L;
 60         } else {
 61             return L;
 62         }
 63     }
 64     int M = L + (R - L) / 2;
 65     if(r < M + 1) return query(l, r, add + addv[o], lson);
 66     int minr = query_min(M + 1, min(r, R), 0, 1, 1, len);
 67     if(minr < 2) return query(l, r, add + addv[o], rson);
 68     return query(l, r, add + addv[o], lson);
 69 }
 70 int main() {
 71     int n, q; set<int> fir;
 72     scanf("%d%d", &n, &q);
 73     scanf("%s", str + 1);
 74     len = n;
 75     for(int i = 1 ; i <= len ; i++)
 76         if(str[i] == '(') num[i] = 1;
 77         else {
 78             num[i] = -1;
 79             fir.insert(i);
 80         }
 81     for(int i = 1 ; i <= len ; i++) num[i] += num[i - 1];
 82     for(int i = 1 ; i <= len ; i++) update(i, num[i], 1, 1, len);
 83     //cout << query_min(1, 1, 0, 1, 1, len) << "!!" << endl;
 84     for(int i = 0 ; i < q ; i++) {
 85         //cout << str + 1 << endl;
 86         int pos; scanf("%d", &pos);
 87         if(str[pos] == '(') {
 88             str[pos] = ')';
 89             fir.insert(pos);
 90             int pp = *fir.begin();
 91             fir.erase(fir.begin());
 92             add(pos, len, -2, 1, 1, len);
 93             add(pp, len, 2, 1, 1, len);
 94             printf("%d
", pp);
 95             str[pp] = '(';
 96         } else { // str[pos] == ')'
 97             str[pos] = '(';
 98             add(pos, len, 2, 1, 1, len);
 99             fir.erase(pos);
100             int pp = query(1, pos, 0, 1, 1, len);
101             //cout << pp << "~~" << endl;
102             pp++;
103             str[pp] = ')';
104             fir.insert(pp);
105             add(pp, len, -2, 1, 1, len);
106             printf("%d
", pp);
107         }
108     }
109     return 0;
110 }