L Yet Another Bracket Sequence

题目地址：

https://ac.nowcoder.com/acm/contest/5795/L

基本思路：

其实感觉这题比较简单，但是过题人数好像不太多，我们先思考一下不带修改的括号匹配的过程，很明显我们可以定义一个遇到 ( 就加一，遇到 ) 就减一，然后只要整个过程中都大于等于零，并且最后等于就说明括号匹配是成功的。那么我们想按照题目修改后会怎么样，其实很容易发现，如果将当前位置的 ( 变为 ) 实际上就是将之后的全部减二，同理如果 ) 变为 ( 其实就是将之后的全部加二。那么我们很容易发现上面的过程和判断包含了区间修改，区间查询和单点查询，所以我们只要用线段树维护修改的过程，每次查询整体的最小是不是大于等于，并且最后等于就行了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = (int)1e5+10;
struct Node{
    int l,r,sum,mn,lazy;
}tr[maxn*4];
int a[maxn];
inline void push_up(int index){//向上更新;
  tr[index].sum = tr[index<<1].sum + tr[index<<1|1].sum;
  tr[index].mn = min(tr[index<<1].mn,tr[index<<1|1].mn);
}
inline void push_down(int index){//向下传递lazy标记;
  if(tr[index].lazy){
    tr[index<<1].sum += tr[index].lazy*(tr[index<<1].r-tr[index<<1].l+1);
    tr[index<<1|1].sum += tr[index].lazy*(tr[index<<1|1].r-tr[index<<1|1].l+1);
    tr[index<<1].mn += tr[index].lazy;
    tr[index<<1|1].mn += tr[index].lazy;
    tr[index<<1].lazy += tr[index].lazy;
    tr[index<<1|1].lazy += tr[index].lazy;
    tr[index].lazy = 0;
  }
}
void build(int index,int l,int r){//建树;
  tr[index].l = l,tr[index].r = r;
  if(l==r){
    tr[index].sum = a[l];
    tr[index].mn = a[l];
    return;
  }
  int mid = (l+r)>>1;
  build(index<<1,l,mid);
  build(index<<1|1,mid+1,r);
  push_up(index);
}
void change(int index,int l,int r,int val){//区间修改;
  if(tr[index].l>=l&&tr[index].r<=r){
    tr[index].mn += val;
    tr[index].sum += val*(tr[index].r-tr[index].l+1);
    tr[index].lazy += val;
    return;
  }
  push_down(index);
  int mid = (tr[index].l+tr[index].r)>>1;
  if(r <= mid) change(index<<1,l,r,val);
  else if( l > mid) change(index<<1|1,l,r,val);
  else{
    change(index<<1,l,mid,val);
    change(index<<1|1,mid+1,r,val);
  }
  push_up(index);
}
void update(int index,int val,int x){//单点修改;
  if(tr[index].l == tr[index].r){
    tr[index].sum += val;
    tr[index].mn += val;
    return;
  }
  int mid = (tr[index].l+tr[index].r)>>1;
  if( x <= mid) update(index<<1,val,x);
  else update(index<<1|1,val,x);
  push_up(index);
}
int ask(int index,int x){//单点查询;
  if(tr[index].l==tr[index].r){
    return tr[index].mn;
  }
  push_down(index);
  int mid = (tr[index].l+tr[index].r)>>1;
  if(x <= mid) return ask(index<<1,x);
  else return ask(index<<1|1,x);
}
int query(int index,int l,int r){//区间查询;
  if(tr[index].l>=l&&tr[index].r<=r){
    return tr[index].mn;//查询区间最小;
  }
  push_down(index);
  int mid = (tr[index].l+tr[index].r)>>1;
  if(r<=mid) return query(index<<1,l,r);
  else if( l > mid) return query(index<<1|1,l,r);
  else{
    return min(query(index<<1,l,mid),query(index<<1|1,mid+1,r));//查询区间最小;
  }
}
string str;
int n,m;
signed main() {
  IO;
  cin >> n >> m;
  cin >> str;
  str = ' ' + str;
  int cnt = 0;
  rep(i,1,n){
    if(str[i] == '(') cnt++;
    else cnt--;
    a[i] = cnt;
  }
  build(1,1,n);
  while (m--){
    int x;
    cin >> x;
    if(str[x] == '('){
      str[x] = ')';
      change(1,x,n,-2);
    }else{
      str[x] = '(';
      change(1,x,n,2);
    }
    if(ask(1,n) == 0 && query(1,1,n) >= 0) cout << "Yes" << '\n';
    else cout << "No" << '\n';
  }
  return 0;
}