AOJ 1351 Flipping Parentheses

解法

StarrySkyTree + 二分探索で通した.

( を +1, ) を -1 として累積和をStarrySkyTree上で管理する.
文字列が balanced であることと,累積和上の最小値が 0 以上であり,かつ末尾の値が0であることは同値である.

さて,与えられた位置をとりあえず反転して考える.

( -> ) に反転した場合,明らかに反転後最も左に現れる ) の位置が答えになる(証明も簡単).

) -> ( に反転した場合が問題である.
ある位置の ( を ) に反転できる条件は,それ以降の累積和の値の最小値が2以上であることに気がつけば,二分探索で求めるだけになる.

計算量は O(N(logN)^2) となる.

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int inf = 1e9;

class starry_sky_tree {
public:
    starry_sky_tree(int n_)
    : n(expand(n_)), data(n * 2, 0), lazy(n * 2, 0)
    {}

    void add(int l, int r, int val) {
        l += n, r += n;
        const int left = l, right = r;
        while(l != r) {
            if(l & 1) {
                lazy[l] += val;
                data[l++] += val;
            }
            if(r & 1) {
                lazy[--r] += val;
                data[r] += val;
            }
            l /= 2, r /= 2;
        }
        l = left, r = right - 1;
        while(l /= 2, r /= 2) {
            data[l] = min(data[l * 2], data[l * 2 + 1]) + lazy[l];
            data[r] = min(data[r * 2], data[r * 2 + 1]) + lazy[r];
        }
    }

    int query(int l, int r) const {
        l += n, r += n;
        int res1 = inf, res2 = inf;
        while(l != r) {
            if(l & 1) res1 = min(res1, data[l++]);
            if(r & 1) res2 = min(res2, data[--r]);
            l /= 2, r /= 2;
            res1 += lazy[l - 1];
            res2 += lazy[r];
        }
        --l;
        while(l /= 2, r /= 2) {
            res1 += lazy[l];
            res2 += lazy[r];
        }
        return min(res1, res2);
    }

private:
    int expand(int n) {
        return n == 1 ? n : expand((n + 1) / 2) * 2;
    }

private:
    const int n;
    vector<int> data, lazy;
};

int main() {
    int N, Q;
    string s;
    cin >> N >> Q >> s;

    starry_sky_tree sum(N);
    set<int> right_paren;
    for(int i = 0; i < N; ++i) {
        if(s[i] == '(') {
            sum.add(i, N, 1);
        } else {
            sum.add(i, N, -1);
            right_paren.insert(i);
        }
    }

    while(Q--) {
        int q;
        cin >> q;
        q--;

        int ans = q;
        if(s[q] == '(') {
            sum.add(q, N, -2);
            right_paren.insert(q);
            ans = *right_paren.begin();
            right_paren.erase(ans);
            sum.add(ans, N, 2);
        } else {
            sum.add(q, N, 2);
            int lb = 0, ub = N - 1;
            while(ub - lb > 1) {
                const int mid = (lb + ub) / 2;
                if(sum.query(mid, N) >= 2) {
                    ub = mid;
                } else {
                    lb = mid;
                }
            }
            ans = ub;
            sum.add(ans, N, -2);
            right_paren.erase(q);
            right_paren.insert(ans);
        }
        swap(s[q], s[ans]);

        cout << ans + 1 << endl;
    }
}

感想

swap(s[q], s[ans]) を書き忘れて WA をもらってしまった.