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 をもらってしまった.