做这个题可以熟悉一下线段树的应用。
首先设‘(‘值为1，‘)‘值为1，维护一个前缀和，那么字符串平衡的条件便是到任意位置的前缀和都大于0（左括号数量大于等于右括号数量）并且左右括号数量相等。
当把\(pos\)位置的左括号变为右括号时，相当于把\([pos, n]\)区间内的前缀和都减2（1变成-1）。那么根据上述平衡条件，我们只需要把最左边一个右括号转为左括号。这个可以用\(set\)维护，每发现一个右括号就把它的位置\(insert\)到set里，用的时候只要使用\(upper\_bound()\)函数就能得到我们需要的位置，再\(erase()\)即可。
当把\(pos\)位置的右括号变为左括号时，相当于把\([pos, n]\)区间内的前缀和都加2（-1变成1）。虽然仍然满足第一个平衡条件，但为了保持左右括号数目相等，我们仍需翻转一个左括号，而翻转\(id\)位置的左括号会使\([id, n]\)区间内的前缀和减2，所以我们要找的位置id必须满足\([id, n]\)区间上的最小值大于等于2（不然前缀和会有小于0）。区间最小值用线段树维护，id用二分查找。
#include <bits/stdc++.h>
typedef long long ll;
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 300005;
int a[maxn];
int n, m;
set<int> l;
struct node{
int l, r;
ll Min;
ll addv;
}tree[4*maxn];
void build(int o, int l, int r)
{
tree[o].l = l;
tree[o].r = r;
if(l==r){
tree[o].Min = a[l];
return;
}
int mid = (l+r)>>1;
build(o*2, l, mid);
build(o*2+1, mid+1, r);
tree[o].Min = min(tree[o*2].Min, tree[o*2+1].Min);
}
void spread(int o)
{
if(tree[o].addv){
tree[o*2].addv += tree[o].addv;
tree[o*2+1].addv += tree[o].addv;
tree[o*2].Min += tree[o].addv;
tree[o*2+1].Min += tree[o].addv;
tree[o].addv = 0;
}
}
void change(int o, int l, int r, int k){
if(tree[o].l>=l && tree[o].r<=r){
tree[o].Min += k;
tree[o].addv += k;
return;
}
spread(o);
int mid = (tree[o].l+tree[o].r)>>1;
if(l<=mid) change(o*2, l, r, k);
if(r>mid) change(o*2+1, l, r, k);
tree[o].Min = min(tree[o*2].Min, tree[o*2+1].Min);
return;
}
ll ask(int o, int l, int r)
{
if(tree[o].l>=l && tree[o].r<=r){
return tree[o].Min;
}
spread(o);
ll res = INF;
int mid = (tree[o].l+tree[o].r)>>1;
if(l<=mid) res = min(res, ask(o*2, l, r));
if(r>mid) res = min(res, ask(o*2+1, l, r));
return res;
}
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
cin >> n >> m;
string s;
cin >> s;
for(int i=1; i<=n; i++){
if(s[i-1]==‘(‘) a[i] = a[i-1]+1;
else{
a[i] = a[i-1]-1;
l.insert(i);
}
}
build(1, 1, n);
for(int i=1; i<=m; i++){
int q;
cin >> q;
if(s[q-1]==‘(‘){
s[q-1] = ‘)‘;
l.insert(q);
change(1, q, n, -2);
int pos = *l.upper_bound(0);
change(1, pos, n, 2);
l.erase(pos);
s[pos-1] = ‘(‘;
printf("%d\n", pos);
}
else{
l.erase(q);
s[q-1] = ‘(‘;
change(1, q, n, 2);
int ll = 1, rr = q;
while(rr-ll>1){
int mid = (ll+rr)>>1;
if(ask(1, mid, q)>=2) rr=mid;
else ll=mid;
}
s[rr-1] = ‘)‘;
l.insert(rr);
change(1, rr, n, -2);
printf("%d\n", rr);
}
}
return 0;
}
2014-2015 ACM-ICPC, Asia Tokyo Regional Contest - G - Flipping Parentheses
原文：https://www.cnblogs.com/DinoMax/p/13860915.html