codeforces 1263E

Editor 线段树

把 ( 记为1，把 ) 记为-1
所以：
1、找最大括号的匹配深度计算最大前缀和就行了
2、判断修改当前位置之后是否能够完美匹配括号 需要判断两个条件：
(1) 总体前缀和是否为0
(2) 判断最小前缀和是不是负的，如果最小前缀和出现负的那么说明左右括号位置反了

#include <bits/stdc++.h>using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, q;struct info
{int sum, smax, smin;
};struct Node
{info val;
} segs[N * 4];// 最大前缀和，最小前缀和，前缀和
info operator + (const info &l, const info &r)
{info a;a.sum = l.sum + r.sum;a.smax = max(l.smax, l.sum + r.smax);a.smin = min(l.smin, l.sum + r.smin);return a;
}void update(int id)
{segs[id].val = segs[id * 2].val + segs[id * 2 + 1].val;
}void build(int id, int l, int r)
{if(l == r) segs[id].val = {a[l], a[l], a[l]};else{int mid = l + r >> 1;build(id * 2, l, mid);build(id * 2 + 1, mid + 1, r);update(id);}
}void change(int id, int l, int r, int pos, int val)
{if(l == r) segs[id].val = {val, val, val};else{int mid = l + r >> 1;if(pos <= mid) change(id * 2, l, mid, pos, val);else change(id * 2 + 1, mid + 1, r, pos, val);update(id);}
}int main()
{cin >> n;string s;cin >> s;int pos = 1;for(char it : s){if(it == '('){change(1, 1, n, pos, 1);}else if(it == ')'){change(1, 1, n, pos, -1);}else if(it == 'L'){if(pos > 1) pos --;}else if(it == 'R') pos ++;else change(1, 1, n, pos, 0);// 线段树拿出根节点就可以获得整个数的信息auto root = segs[1].val;if(root.sum != 0 || root.smin < 0)printf("-1 ");else printf("%d ", root.smax);}
}