题目链接： 点击打开链接
题目大意:给一个括号已经匹配好的序列，每次反转一个括号，然后让你再次反转一个括号再次使得括号匹配，并且你反转的位置尽可能的靠近左端。
可以对于每个位置，，记录它之前的左括号的数量减去右括号的数量，这个序列合法的条件就是每个位置不会出现值小于0的情况。最后一位一定是0.
如果他反转的是右括号，这个位置变成左括号之后你需要找到一个左括号把它反成右括号。而你需要找的位置就是从最后一个往前最后一个为大于等于2的位置。
如果他反转的是左括号，那就找到最左边的右括号。
两种情况分别都可以用线段树维护
#include <algorithm>#include <cstdio>#include <cmath>#include <cstring>#include <cstdlib>#include <iostream>#define MAX 0x3f3f3f3f#define N 300005#define mod 1000000007#define lson o<<1, l, m#define rson o<<1|1, m + 1, rtypedef long long LL;const double pi = acos(-1.0);using namespace std;int n, q, X, A, B, mi[N<<2], add[N<<2];bool E, v[N<<2];char s[N];void down(int o) {if(add[o]) {add[o<<1] += add[o];add[o<<1|1] += add[o];mi[o<<1] += add[o];mi[o<<1|1] += add[o];add[o] = 0;}}void modify(int o, int l, int r) {if(l == r) v[o] = E;else {int m = (l+r) >> 1;if(X <= m) modify(lson);else modify(rson);v[o] = v[o<<1] | v[o<<1|1];}}void build(int o, int l, int r) {if(l == r) mi[o] = A;else {int m = (l+r) >> 1;if(X <= m) build(lson);else build(rson);mi[o] = min(mi[o<<1], mi[o<<1|1]);}}void update(int o, int l, int r) {if(X <= l && r <= n) {add[o] += B;mi[o] += B;} else {down(o);int m = (l+r) >> 1;if(X <= m) update(lson);if(m < n ) update(rson);mi[o] = min(mi[o<<1], mi[o<<1|1]);}}int Find(int o, int l, int r) {if(l == r) return l;else {int m = (l+r) >> 1;if(v[o<<1]) return Find(lson);else return Find(rson);}}int query(int o, int l, int r) {if(l == r) return mi[o] >= 2;else {down(o);int m = (l+r) >> 1, res = 0;if(mi[o<<1|1] >= 2) {res += r-m;res += query(lson);} else res += query(rson);return res;}}int main(){//freopen("in.txt", "r", stdin);//read(n), read(q);scanf("%d%d", &n, &q);scanf("%s", s+1);int zuo = 0, you = 0;for(X = 1; X <= n; X++) {if(s[X] == '(') zuo++;else {you++;E = 1, modify(1, 1, n);}A = zuo – you;build(1, 1, n);}while(q–) {scanf("%d", &X);if(s[X] == '(') {s[X] = ')';// 修改成右括号B = -2, update(1, 1, n);E = 1, modify(1, 1, n);X = Find(1, 1, n); // 找到第一个右括号的位置printf("%d\n", X);s[X] = '(';// 将它改为左括号B = 2, update(1, 1, n);E = 0, modify(1, 1, n);} else {s[X] = '(';//修改成左括号B = 2, update(1, 1, n);E = 0, modify(1, 1, n);X = n – query(1, 1, n) + 1; // 找到满足条件的最左边的左括号printf("%d\n", X);s[X] = ')'; //将它修改成右括号B = -2, update(1, 1, n);E = 1, modify(1, 1, n);}}return 0;}
不要因为生活琐事而烦恼,不要因为儿女情长而忧愁,
