ICPCアジア地区予選 2014 G - Flipping Parentheses
Flipping Parentheses | Aizu Online Judge
セグ木の練習がしたい + 括弧列の問題がすきということで難しい問題にチャレンジ．
問題概要
長さNのバランスの取れた括弧列が与えられる．これに対し，Q個のクエリが与えられる．クエリは以下の内容である．
括弧列の左からq番目の括弧をひっくり返し，バランスの取れていない括弧列にする．これを1つだけ括弧をひっくり返すことでバランスの取れた括弧列に戻す．このとき，ひっくり返すべき括弧が左からi番目の括弧であるときiを出力する．条件を満たすiが複数ある場合，最小のものを出力する．
($ 1 \leq N \leq 3 \times 10^5$, $ 1 \leq Q \leq 1.5 \times 10^5$)
解法概要
制約より，1クエリあたり O(logN)ぐらいで処理できたらなぁという気持ちになる．
括弧列の問題でときどきある，'(' を +1，')' を -1とした累積和で「バランスが取れている」「 '(' が多い」「 ')' が多い」の判断ができそう，そうすれば括弧をひっくり返すときもセグ木の範囲加算クエリでいい感じに計算量を減らせそうかなぁという気持ちにもなる． セグ木で各インデックスiに対する[1,i]の括弧の値の累積和を保持しておいて，ひっくり返した括弧の位置以降の値を+2か-2すれば良いからである．
ひっくり返す前の括弧が '(' だったか ')' でやるべき処理が分かれる．
ひっくり返す前の括弧が '(' だったとき
これはサンプルでいう((())→()))) (3番目がひっくり返される) のような場合．
この場合は簡単で，括弧列を左から見ていって1番最初の ')' を'(' にひっくり返せばバランスの取れた括弧列になる．バランスの取れた括弧列を左から見ていったとき，')' が '(' より多くなることがあってはならないが，'(' が ')' より多くなるぶんには構わないし，答えるべきは条件を満たす最も左の括弧だからである．
')' の位置を set で持っておけば O(logN) で処理できる．
ひっくり返す前の括弧が ')' だったとき
これは ((()))→(((()) (4番目がひっくり返される)のような場合．これはひっくり返す前の括弧が '(' の場合に比べると難しい．
この場合，バランスの取れた括弧列に戻すにはどこかの '(' を ')' にする必要があるが，適当にやるとどこかで ')' が '(' より多くなる (= すでに説明した方法での累積和が負になる) ことが発生しうる． '(' を ')' にすると，その位置以降での値は2ずつ減る．そのため，i番目の括弧をひっくり返すとき，[i, N]での最小値は少なくとも2でなければならない．この条件を満たすiを二分探索で計算すると O(logN)，セグ木に保持された累積和について，[i,N]にそれぞれ -2 する処理が O(logN) なので，これも O(logN) で処理可能．
実装のポイント
書いてみると滅茶苦茶に難しいわけではないのだが，実装にかなり時間がかかってしまった……．ポイントは
- ')' の位置を set で管理
- ひっくり返す前の括弧がどちらだったかの判定のため，sは各処理に合わせて随時更新
- 最小値なのでセグ木のdataを大きな値で初期化するが，lazyは0で初期化する (それはそう)
- ただし，データへのアクセスが起きたらdata[i]はinfから0に更新する
ソースコード
#include <iostream> #include <vector> #include <set> #include <algorithm> #include <climits> using namespace std; template<typename T> class LazyRMQ { public: int n; T inf = INT_MAX; vector<T> data, lazy; LazyRMQ(int m, T init_value=INT_MAX){ // 2のべき乗にする n = 1; while(n < m) n <<= 1; data.assign(2*n-1, init_value); lazy.assign(2*n-1, 0); } void eval(int k, int kl, int kr){ if(data[k] == inf) data[k] = 0; if(lazy[k] == 0) return; data[k] += lazy[k]; if(kr - kl > 1){ lazy[2*k+1] += lazy[k]; lazy[2*k+2] += lazy[k]; } lazy[k] = 0; } // [s,t) void add(int s, int t, int k, int kl, int kr, T x){ eval(k, kl, kr); if(kr <= s || t <= kl) return; if(s <= kl && kr <= t){ lazy[k] += x; eval(k, kl, kr); return; } int kc = (kl+kr)/2; add(s, t, 2*k+1, kl, kc, x); add(s, t, 2*k+2, kc, kr, x); data[k] = min(data[2*k+1], data[2*k+2]); } // [s,t) T find(int s, int t, int k, int kl, int kr){ eval(k, kl, kr); if(kr <= s || t <= kl) return inf; if(s <= kl && kr <= t) return data[k]; int kc = (kl+kr)/2; T vl = find(s, t, 2*k+1, kl, kc); T vr = find(s, t, 2*k+2, kc, kr); return min(vl, vr); } }; int main(){ int n,Q,q; scanf("%d %d", &n, &Q); LazyRMQ<int> rmq(n+1); char s[n+1]; scanf("%s", s); set<int> close; int data[n+1]; data[0] = 0; for(int i=0;i<n;i++){ if(s[i]=='('){ data[i+1] = data[i]+1; }else{ data[i+1] = data[i]-1; close.insert(i+1); } rmq.add(i+1, i+2, 0, 0, rmq.n, data[i+1]); } for(int i=0;i<Q;i++){ scanf("%d", &q); // 今回の変更により，閉じかっこが開いたか？ bool open_parentheses = (s[q-1] == ')'); int j; if(open_parentheses){ rmq.add(q, rmq.n, 0, 0, rmq.n, 2); s[q-1] = '('; close.erase(q); // どこかの開きかっこを閉じる // 「以降全て2以上」のところはひっくり返せる j = (n+1)/2; int ng = 0, ok = n; while(ok-ng > 1){ j = (ng+ok)/2; if(rmq.find(j, rmq.n, 0, 0, rmq.n) >= 2){ ok = j; }else{ ng = j; } } j = ok; rmq.add(j, rmq.n, 0, 0, rmq.n, -2); s[j-1] = ')'; close.insert(j); }else{ rmq.add(q, rmq.n, 0, 0, rmq.n, -2); s[q-1] = ')'; close.insert(q); // どこかの閉じかっこを開く // 先頭の閉じかっこをひっくり返せば良い j = *close.begin(); rmq.add(j, rmq.n, 0, 0, rmq.n, 2); s[j-1] = '('; close.erase(j); } printf("%d\n", j); } }
所感
1日あたりの使用時間は長くないけど遅延評価セグ木の勉強などもあわせると1週間ぐらいかかってしまった．
