AOJ 1351 Flipping Parentheses
問題文
ICPC Asia 2014 Tokyo G
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1351
解法
想定解法と違うけど通ってしまった
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1174168#1
(を1、)を0とみなして01列として扱って、64bitまとめて操作する
各64bitごとに、予めdiffとdiffの下限(後述)を計算して持っておく。
ここで、diffとは1と0の数の差で次のようになる(例では16bit)
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| diff | 1 | 0 | 1 | 0 | 1 | 0 | -1 | -2 | -1 | -2 | -1 | -2 | -1 | 0 | -1 | 0 |
| diffの下限 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -2 | -2 | -2 | -2 | -2 | -2 | -2 | -2 | -2 |
この場合はdiffは0、diffの下限は-2となる。
(を反転させるクエリでは、最初の)を反転させれば良いから、diffが64でない最初の場所から探せばよい。
)を反転させるクエリでは、配列の先頭から直前の要素までのdiffの合計+今見ている要素のinfが1以下になる最後の場所から探せばよい。
各クエリで変更されるのは高々2bitなので、高々2箇所についてdiffとdiffの下限を更新すればよい。
これで計算量が64分の1程度になって通る(平方分割に近そう)
計算量
O(NQ/(bit幅)+Q(bit幅))
本番は区間に加算、区間の最小値のSegmentTreeを書こうとして盛大にバグって解けなかったのに、こんなので通ってしまうとは…
