考察
行を初めて黒塗りすると全Nマスが増え、二回目以降に増えるのは前回操作後に一度以上白塗りされた列数である。同じ列への複数操作は最後の時刻一つだけ数えればよい。
採用する候補: query時刻軸のFenwick treeに各列の最新type2時刻だけ1を置き、行Rの前回type1時刻以後の1数をrange sumして黒数を更新する。行列を入れ替えた対称構造も同時に持つ。
棄却する候補: N×N盤面の各cell色を保持し、行・列操作ごとにNマスを塗り替える。
N,Qが大きく一query O(N)、盤面memory O(N^2) は不可能である。
列latest type2を表すBITと行latest type1を表すBIT、rowLast・colLastを用意する。type1はrowLast=0ならN、そうでなければそれ以後の列latest数を加える。type2はcolLast以後の行latest数を引き、自typeのlatest markerを更新する。
典型の発動条件
最新出現時刻のFenwick管理
発動条件: 前回時刻以後に現れたdistinct key数をonlineで問いたいとき。
各keyのlatest位置だけ1にして時刻区間和を取る。
行列操作の対称処理
発動条件: row全体とcolumn全体への上書きが交互に来るとき。
二方向に同じlast-event構造を持ち黒数差分だけ更新する。
問題固有の要素
上書き後の差分はcell状態ではなく、対象行/列の前回時刻より新しい反対方向operationのdistinct数で決まる。
別の問題へ持ち帰る視点: 『区間内に一度以上現れた値』はofflineでなくてもlatest位置indicatorのrange sumで数えられる。
正当性
列Cに新しいtype2が来たら旧latest時刻の1を0、新時刻を1にして、distinct列を一つだけ表す。 行Rの初回type1では増加数をNとし、列Cのtype2ではcolLast[C]以後に最新type1を持つdistinct行数を減少数とする。 latest event代表により時刻区間内に一度でも現れたdistinct列数がFenwick sumと一致し、行ごとのlast時刻で必要区間を定められる。
実装上の注意
- 初回操作の番兵時刻0と初期色を正しく式へ入れ、BIT更新で旧latestを必ず消す。黒数はN^2までなので64 bitを使う。
復習の核
- 同じ列を複数回白塗りした後に一行を黒塗りする例で、latest markerだけがdistinct列数を表すことを確認する。
計算量と制約
時間
O(Q log Q)、N×N盤面を時刻latest代表で処理。
空間
O(Q)、触れた行列のlastと二BIT。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N, Q \leq 3 \times 10^5; For type 1 queries, 1 \leq R \leq N.; For type 2 queries, 1 \leq C \leq N.; All input values are integers.
出典