考察
各bitは独立し、prefix操作列は{0,1}上の関数である。各bitの関数は入力0,1に対する出力(f(0),f(1))の二値だけで表せるため、30bit分を二つのmaskとして保持する。新しいAND/OR/XOR操作を二出力へ適用してprefix関数を更新し、前回のXへその関数を一度適用すればよい。関数合成は結合的なので、逐次更新でも各prefixの作用は変わらない。
典型の発動条件
bit ごとの独立化
発動条件: AND・OR・XOR だけからなる操作列で、bit 間の桁上がりや依存がないとき。
30 個の bit を独立な二値関数として処理し、最後に整数へまとめる。
有限関数の prefix 合成
発動条件: 小さな有限集合上の関数を順に合成し、各 prefix の写像を求めるとき。
全入力に対する出力表を状態として、新関数を表の各値へ作用させる。
問題固有の要素
30 bit 分の f(0),f(1) は二本の整数 mask f0,f1 として同時に保持でき、X の 0 bit には f0、1 bit には f1 を選べる。
別の問題へ持ち帰る視点: 同型な小状態を全 bit に持つ場合、bitset 的な整数演算で状態遷移を並列化する。
正当性
i 番目の手続きは操作 i だけでなく合成済みの操作 1,…,i を前回の X に再適用するため、prefix 関数そのものを保持する必要がある。 新しい操作は二つの出力値へ適用するだけで合成でき、各 prefix の効果を定数個の bit 演算へ圧縮できる。
実装上の注意
- 初期写像は f0=0、f1=(1<<30)−1 の恒等関数とし、新操作を f0 と f1 の両方へ適用する。
- X の更新は ((NOT X) AND f0) OR (X AND f1) とし、NOT の上位 bit は30 bit maskで切り落とす。
復習の核
- bitwise 操作列では各 bit の入力候補が 0 と 1 しかないことから、合成関数を真理値表で持てないか考える。
- 問題文の各段階が前回状態へ何を再適用するかを小例で追い、単なるオンライン一操作と取り違えない。
計算量と制約
時間
O(NB)、B=30。bitmask並列ならO(N)。
空間
O(1)、f(0),f(1),現在X。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2\times 10^5; 1\leq T_i \leq 3; 0\leq A_i \lt 2^{30}; 0\leq C \lt 2^{30}; All values in input are integers.
出典