https://codeforces.com/problemset/problem/1095/E
【题意】
问有多少的个位置，更换一个括号，就能使括号匹配
【思路】
线段树维护。
遍历每一个位置，单点修改。建一棵线段树，树上节点维护两个信息：左括号数，右括号数
区间合并：
假设左儿子为：))(((，右儿子为：))(((，合并消除()之后就变成了))((((
所以我可以从1枚举到n，在线段树中改变第 i 个位置的括号，如果线段树根节点的tl=tr=0，那么答案就++。
暴力修改，线段树维护
【代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
char s[maxn];
int tl[maxn * 4], tr[maxn * 4];void push(int p, int ls, int rs)
{if (tr[ls] >= tl[rs]){tl[p] = tl[ls];tr[p] = tr[rs] + tr[ls] - tl[rs];}else{tr[p] = tr[rs];tl[p] = tl[ls] + tl[rs] - tr[ls];}
}void build(int p, int l, int r)
{if (l == r){if (s[l] == '(')tr[p] = 1;else tl[p] = 1;return;}int m = (l + r) / 2, ls = p * 2, rs = p * 2 + 1;build(ls, l, m);build(rs, m + 1, r);push(p, ls, rs);
}void up(int p, int l, int r, int k)
{if (l == r){tl[p] = !tl[p];tr[p] = !tr[p];return;}int m = (l + r) / 2, ls = p * 2, rs = p * 2 + 1;if (k <= m)up(ls, l, m, k);else up(rs, m + 1, r, k);push(p, ls, rs);
}int main()
{int n;while (~scanf("%d", &n)) {int ans = 0;scanf("%s", s + 1);build(1, 1, n);for (int i = 1; i <= n; i++){up(1, 1, n, i);if (tl[1] == 0 && tr[1] == 0)ans++;up(1, 1, n, i);}cout << ans;}
}