http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1542
赛后发现这套题是2014东京区域赛的题目，看了排名才发现自己有多low = =！
题目大意是这样的，给一个已经匹配了的括号序列，现每次操作就是在位置p将这个位置的括号反转，问要达到将这个序列重新变成匹配序列，最左侧能够操作第几个括号达到目的。
这里，我的思路是用一个数组a，a[i]表示的是前i个括号，左括号'('与右括号')'的数量之差，题目数据就可以表示为：
s: ( ( ( ) ) )
a: 1 2 3 2 1 0
这样，一个匹配的括号序列对应的数组一定满足两个条件：1、数组没有一个元素为负 2、数组是以0结尾
现操作时，若是将'(' 转化为')' ,比如将位置4的括号反转,对应数组：
s: ( ( ( ( ) )
a: 1 2 3 4 3 2
可以看做是将数组位置4以后的每个元素都+2(反之，若是')'转化为'(',那么就是那个位置以后每个元素都-2)
可以看到：
对应第一种操作，将'(' 转化为')'， 要达到匹配序列，只需要将括号序列里的第一个右括号')'翻转即可（因为此时为+2操作，又只可以操作右括号，所以操作第一个必然是最优的）
对应第二种操作，将')'转化为'('，则是找到从末尾往前找到最早的一个a[p]>=2的位置p，且a[p ~ n] >= 2全部成立，(因为是-2操作，所以必须保证在-2前这个数是>=2的)
计算时，可以使用线段树(因为有区间操作),节点保存的内容包括左右括号数量之差a，延时标记s，以及f = a[i] - i的值（若a[i] - i < 0，说明在区间[1, i]一定存在一个左括号，供查找第一个左括号时使用）,而若要找到从后往前最长连续的a[p ~ n] >= 2的位置p，只需要判断区间的最小值是否>=2，查找方式与上一个类似。
查询时区间保存的是这个区间的 a 值和 f 值的最小值。区间修改+极值查询。
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf (-((LL)1<<40))
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)
#define rep(i, a, b) for(int i = a; i <= b; i ++) template<class T> T CMP_MIN(T a, T b) { return a < b; }
template<class T> T CMP_MAX(T a, T b) { return a > b; }
template<class T> T MAX(T a, T b) { return a > b ? a : b; }
template<class T> T MIN(T a, T b) { return a < b ? a : b; }
template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; } //typedef __int64 LL;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const double eps = 1e-; int n, q, p, len;
char s[]={""};
struct Node {
int f, a, s;
}t[<<]; char rev(char c) { return (c == '(') ? ')' : '('; } void buildTree(int k, int L, int R, int p, int a)
{
t[k].s = ;
if(L == R) {
t[k].f = a - L; t[k].a = a;
return ;
}
int mid = (L + R) >> ;
if(p > mid) buildTree(rson, p, a);
else buildTree(lson, p, a);
t[k].f = min(t[k<<].f, t[k<<|].f);
t[k].a = min(t[k<<].a, t[k<<|].a);
} void init()
{
mem0(t);
int sum = ;
len = strlen(s) - ;
rep (i, , len) {
sum += (s[i] == '(') ? : -;
buildTree(, , len, i, sum);//建树
}
} //向下传延时标记
void pushDown(int k)
{
t[k<<].s += t[k].s; t[k<<].a += t[k].s; t[k<<].f += t[k].s;
t[k<<|].s += t[k].s; t[k<<|].a += t[k].s; t[k<<|].f += t[k].s;
t[k].s = ;
} //更新操作,将区间[p, len]的所有值都+val
void update(int k, int L, int R, int p, int val)
{
if(p <= L) {
t[k].s += val;
t[k].a += val;
t[k].f += val;
return ;
}
pushDown(k);
int mid = (L + R) >> ;
if(p <= mid) update(lson, p, val);//左侧可能需要更新
update(rson, p, val);//右侧是一定要更新的,因为需要更新的区间为[p, len]
t[k].f = min(t[k<<].f, t[k<<|].f);
t[k].a = min(t[k<<].a, t[k<<|].a);
} //查询最左侧的右括号
int query1(int k, int L, int R)
{
if(L == R) return L;
int mid = (L + R) >> ;
pushDown(k);
if(t[k<<].f < ) return query1(lson);
return query1(rson);
} //查询从len往前连续的最长的满足a>=2的点，也就是最后一个<2的位置+1
int query2(int k, int L, int R)
{
if(L == R) return min(len, L + );
int mid = (L + R) >> ;
pushDown(k);
if(t[k<<|].a < ) return query2(rson);
return query2(lson);
} int main()
{
//FIN;
while(~scanf("%d %d%*c %s", &n, &q, s + )) {
init();
rep (i, , q - ) {
scanf("%d", &p);
s[p] = rev(s[p]); update(, , len, p, s[p] == ')' ? - : );
if(s[p] == ')') p = query1(, , len);//find first )
else p = query2(, , len); //find last < 2
s[p] = rev(s[p]); update(, , len, p, s[p] == ')' ? - : );
printf("%d\n", p);
}
}
return ;
}