题目链接：点击打开链接
文章转载自：xuanqis.com
转载注明出处…Description
A string consisting only of parentheses ‘(’ and ‘)’ is called balanced if it is one of the following.
A string “()” is balanced.
Concatenation of two balanced strings are balanced.
When a string s is balanced, so is the concatenation of three strings “(”, s, and “)” in this order.
Note that the condition is stronger than merely the numbers of ‘(’ and ‘)’ are equal. For instance, “())(()” is not balanced.
Your task is to keep a string in a balanced state, under a severe condition in which a cosmic ray may flip the direction of parentheses.
You are initially given a balanced string. Each time the direction of a single parenthesis is flipped, your program is notified the position of the changed character in the string. Then, calculate and output the leftmost position that, if the parenthesis there is flipped, the whole string gets back to the balanced state. After the string is balanced by changing the parenthesis indicated by your program, next cosmic ray flips another parenthesis, and the steps are repeated several times.
Input
The input consists of a single test case formatted as follows.
N Qsq1⋮qQ
The first line consists of two integers N and Q (2 ≤ N ≤ 300000, 1 ≤ Q ≤ 150000). The second line is a string s of balanced parentheses with length N. Each of the following Q lines is an integer qi (1 ≤ qi ≤ N) that indicates that the direction of the qi-th parenthesis is flipped.
Output
For each event qi, output the position of the leftmost parenthesis you need to flip in order to get back to the balanced state.
Note that each input flipping event qi is applied to the string after the previous flip qi − 1 and its fix.
Sample Input
6 3
((()))
4
3
1
20 9
()((((()))))()()()()
15
20
13
5
3
10
3
17
18
Sample Output
2
2
1
2
20
8
5
3
2
2
3
18
Hint
In the first sample, the initial state is “((()))”. The 4th parenthesis is flipped and the string becomes “(((())”. Then, to keep the balance you should flip the 2nd parenthesis and get “()(())”. The next flip of the 3rd parenthesis is applied to the last state and yields “())())”. To rebalance it, you have to change the 2nd parenthesis again yielding “(()())”.
Source
Asia Regional Contest, Tokyo, 2014
思路
首先建树：左括号值为1，右括号值为-1，每个节点依次为从第一个到当前点的和，然后建树，数中维护区间最小值。
然后分析两个操作：即将左括号变为右括号，右括号变为左括号。
1. 左变右：与原先左括号匹配的在当前下标的后面，而将前面的一个右括号变为左括号并不会对匹配影响，都将形成新的匹配，而要求下标最小，所以就将第一个右括号变为左括号。其中寻找最小的使用set维护。
2. 右变左：右变左相对复杂点，需要在前面将一个左括号改成右括号，这会使之后的所有值都减2，不能存在有小于0的值（小于则说明有右括号不能匹配），所以找到最右边的小于2的下标，该下标的右边一定是左括号（比该下标大，为左括号），该左括号就是最小的能改的左括号。
注意修改括号。
感兴趣的可以做一下 北京师范大学第十六届程序设计竞赛决赛的吾好梦中做题 链接
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int MAXN=500010;
char str[MAXN];
int pre[MAXN];
int n, q;
struct Node{
int left;
int right;
int minx; //区间内最大值
int add; //要加的数
}tree[MAXN<<2];
void Build(int l, int r, int v){ //建立线段树
tree[v].left=l;
tree[v].right=r;
tree[v].minx = 0x3f3f3f3f;
tree[v].add=0;
if(l==r){
tree[v].minx = pre[l];
return ;
}
int mid=(l+r)/2;
Build(l,mid,v*2);
Build(mid+1, r, v*2+1);
tree[v].minx=min(tree[v*2].minx, tree[v*2+1].minx);
}
void update(int v, int l, int r, int m){ //更新 l-r 之间的线段树值加 m
if(tree[v].left >= l && tree[v].right <= r){
tree[v].minx += m;
tree[v].add += m;
return ;
}
if(tree[v].add){
tree[v*2].minx += tree[v].add;
tree[v*2+1].minx += tree[v].add;
tree[v*2].add += tree[v].add;
tree[v*2+1].add += tree[v].add;
tree[v].add = 0;
}
int mid = (tree[v].left + tree[v].right)/2;
if(r <= mid){
update(v*2, l, r, m);
}
else if(l > mid){
update(v*2+1, l,r, m);
}
else {
update(v*2, l, r, m);
update(v*2+1, l, r, m);
}
tree[v].minx = min(tree[v*2].minx, tree[v*2+1].minx);
}
int query(int v,int x){ //查询x下标所在位置的值
if(tree[v].left == tree[v].right){
return tree[v].minx;
}
if(tree[v].add){
tree[v*2].minx += tree[v].add;
tree[v*2+1].minx += tree[v].add;
tree[v*2].add += tree[v].add;
tree[v*2+1].add += tree[v].add;
tree[v].add = 0;
}
int mid = (tree[v].left + tree[v].right) / 2;
if(mid >= x) return query(v*2, x);
else return query(v*2+1,x);
}
int asklow(int i, int l, int r, int val){ //返回l到r之间最右边的小于val值的下标
if(tree[i].left >= l && tree[i].right <= r){
if(tree[i].minx >= val) return n+1;
if(tree[i].left == tree[i].right) return tree[i].left;
if(tree[i].add){
tree[i*2].minx += tree[i].add;
tree[i*2+1].minx += tree[i].add;
tree[i*2].add += tree[i].add;
tree[i*2+1].add += tree[i].add;
tree[i].add = 0;
}
if(tree[i*2+1].minx < val) return asklow(i*2+1,l,r,val);
else return asklow(i*2, l, r, val);
}
if(tree[i].add){
tree[i*2].minx += tree[i].add;
tree[i*2+1].minx += tree[i].add;
tree[i*2].add += tree[i].add;
tree[i*2+1].add += tree[i].add;
tree[i].add = 0;
}
int mid = (tree[i].left + tree[i].right) / 2;
int ans = n+1;
if(r>mid) ans = min(asklow(i*2+1, l, r, val),ans);
if(l <= mid && ans == n+1) ans = min(asklow(i*2,l, r, val),ans);
return ans;
}
int main(){
//freopen("2.txt", "r", stdin);
set<int> st;
while(~scanf("%d%d", &n, &q)){ //输入括号个数及操作次数
while(!st.empty())st.clear();
scanf("%s", str+1);
pre[0]=0;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1];
if(str[i]=='('){
pre[i]++;
}
else {
st.insert(i);
pre[i]--;
}
}
Build(1,n,1);
for(int i=1;i<=q;i++){
int numa;
scanf("%d", &numa); //numa为下标
if(str[numa] == '('){ //找到第一个右括号转为左括号
str[numa]=')';
st.insert(numa);
update(1,numa,n,-2);
int temp = *st.begin();
st.erase(temp);
str[temp] = '(';
update(1,temp,n,2);
printf("%d\n",temp);
}
else { //找到第一个小于2的,更新右边的为右括号
str[numa]='(';
st.erase(numa);
update(1,numa,n,2);
int temp = asklow(1,1,n,2);
str[temp+1]=')';
st.insert(temp+1);
printf("%d\n",temp+1);
update(1,temp+1,n,-2);
}
}
}
return 0;
} 
京公网安备 11010502036488号