第三届中国计量大学ACM程序设计竞赛 L-线段树维护前缀最小值

题目链接：https://ac.nowcoder.com/acm/contest/5795/L
给你长度为n的一个扩号序列。m次修改，每次修改把第x个扩号取反方向。并且修改后询问扩号序列是否合法。

思路：用一个线段树维护这个扩号序列
'('：-1
')'：1
每次修改其实就是一个单点修改。如果前缀和<0那么就不合法。如果前缀和>0并且1-n的和为0就合法。

#include <bits/stdc++.h>
using namespace std;

char s[100005];
int sum[4*100005], mi[4*100005];
void gx(int i, int l, int r, int x, int y){
    if(l==r){
        sum[i]=y; return ;
    }
    if(x<=(l+r)/2) gx(i<<1, l, l+r>>1, x, y);
    else gx(i<<1|1, (l+r>>1)+1, r, x, y);
    sum[i]=sum[i<<1]+sum[i<<1|1];
    mi[i]=min(mi[i<<1], mi[i<<1|1]+sum[i<<1]);//维护前缀最小值
}

int main(){

    int n, m;
    scanf("%d%d", &n, &m);
    scanf("%s", s+1);
    for(int i=1; i<=n; i++){
        if(s[i]=='(') gx(1, 1, n, i, 1);
        else gx(1, 1, n, i, -1);
    }
    while(m--){
        int x; scanf("%d", &x);
        if(s[x]=='('){
            gx(1, 1, n, x, -1); s[x]=')';
        }
        else{
            gx(1, 1, n, x, 1);  s[x]='(';
        }
        if(sum[1]==0&&mi[1]>=0){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }

    return 0;
}