题意：给你一长串括号，每次反转一个括号，让你再反转一个括号使得括号平衡，必须要找最右边的那个解。
解题思路：线段树+ set
1）如果将 '('变为 ‘）’ 只需要将最左边那个 ')' 变成 ‘（’即可。
答案
|
2）如果将‘（’变为‘）’ 需要找到 改边位置的前面连续一段前缀和 都大于二 且最前面那个二 例如 前缀和 121012345
|
改变的位置。
解题代码：
1 // File Name: f.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月25日 星期三 13时46分59秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define maxn 310005 26 using namespace std; 27 char str[maxn]; 28 struct nodd{ 29 int l , r , m ,mi,lazy; 30 }tree[maxn*4]; 31 int sum[maxn]; 32 int L(int x) 33 { 34 return 2 *x; 35 } 36 int R(int x) 37 { 38 return 2*x + 1; 39 } 40 void push_up(int c) 41 { 42 tree[c].mi = min(tree[L(c)].mi ,tree[R(c)].mi); 43 } 44 void push_down(int c) 45 { 46 if(tree[c].lazy != 0 ) 47 { 48 tree[L(c)].mi += tree[c].lazy ; 49 tree[R(c)].mi += tree[c].lazy; 50 tree[L(c)].lazy += tree[c].lazy; 51 tree[R(c)].lazy += tree[c].lazy ; 52 tree[c].lazy = 0 ; 53 } 54 } 55 void build(int c, int l ,int r) 56 { 57 tree[c].l = l ; 58 tree[c].r = r; 59 tree[c].m = (l+r)/2; 60 tree[c].lazy = 0 ; 61 if(l == r) 62 { 63 //printf("**%d ",sum[l]); 64 tree[c].mi = sum[l]; 65 return ; 66 } 67 build(L(c),l,tree[c].m); 68 build(R(c),tree[c].m +1, r); 69 push_up(c); 70 } 71 void update(int c, int l , int r ,int v) 72 { 73 if(l <= tree[c].l && r >= tree[c].r) 74 { 75 tree[c].mi += v; 76 tree[c].lazy += v ; 77 return ; 78 } 79 push_down(c); 80 if(l <= tree[c].m) 81 update(L(c),l,r,v); 82 if(r > tree[c].m) 83 update(R(c),l,r,v); 84 push_up(c); 85 } 86 int find(int c, int p ) 87 { 88 //printf("%d %d %d ",c,tree[c].l,tree[c].r); 89 if(tree[c].l == tree[c].r ) 90 { 91 if(tree[c].mi >= 2) 92 return tree[c].l; 93 return 1e9; 94 } 95 push_down(c); 96 if(p <= tree[c].m && p >= tree[c].l) 97 { 98 return find(L(c),p); 99 } 100 int t ; 101 //if(tree[c].l == 1) 102 // printf("***%d ",tree[R(c)].mi); 103 if(tree[R(c)].mi >= 2) 104 t = tree[c].m + 1; 105 else 106 t = find(R(c),p); 107 if(t == tree[c].m + 1) 108 { 109 if(tree[L(c)].mi >= 2 ) 110 return tree[c].l; 111 t = min(t,find(L(c),p)); 112 // printf("***%d %d ",t,); 113 }else{ 114 return t; 115 } 116 } 117 set<int> st; 118 int main(){ 119 int n , m; 120 scanf("%d %d",&n,&m); 121 scanf("%s",&str[1]); 122 for(int i = 1;i <= n;i ++) 123 { 124 125 if(str[i] == ')') 126 { 127 st.insert(i); 128 sum[i] = sum[i-1] - 1; 129 }else{ 130 sum[i] = sum[i-1] + 1; 131 } 132 } 133 build(1,1,n); 134 int q; 135 for(int i = 1;i <= m;i ++) 136 { 137 scanf("%d",&q); 138 if(str[q] == '(') 139 { 140 str[q] = ')'; 141 update(1,q,n,-2); 142 st.insert(q); 143 int t = *st.begin(); 144 printf("%d ",t); 145 st.erase(st.find(t)); 146 update(1,t,n,2); 147 str[t] = '('; 148 }else{ 149 str[q] = '('; 150 st.erase(st.find(q)); 151 update(1,q,n,2); 152 int t = find(1,q); 153 update(1,t,n,-2); 154 str[t] = ')'; 155 st.insert(t); 156 printf("%d ",t); 157 } 158 //puts(&str[1]); 159 } 160 return 0; 161 }