Flipping Parentheses （线段树 单点更新 区间查询）

题目链接 ： 点击打开链接

题目大意 : 给一个括号已经匹配好的序列，每次反转一个括号， 然后让你再次反转一个括号再次使得括号匹配，并且你反转的位置尽可能的靠近左端。

可以对于每个位置，记录它之前的左括号的数量减去右括号的数量，这个序列合法的条件就是每个位置不会出现值小于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, r
typedef 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;
}

Flipping Parentheses （线段树 单点更新 区间查询）

原文：http://blog.csdn.net/u013923947/article/details/44652403