prime's diary

そすうの日々を垂れ流しちゃうやつだよ

AOJ 1351 Flipping Parentheses

問題文

ICPC Asia 2014 Tokyo G

Flipping Parentheses | Aizu Online Judge

解法

想定解法と違うけど通ってしまった

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を書こうとして盛大にバグって解けなかったのに、こんなので通ってしまうとは…