考察
入退室が少ない二人の質問は、その場で区間を突き合わせればよい。入退室が多い人については、その人と全員の同時在室時間をまとめて前計算する。区間の総数は入退室記録の半分なので、前計算が必要な人の数を抑えられる。
以下では入退室の記録数を と書く。記録に付いた時刻 と、記録数 は別の量である。各人は最初も最後も室外にいるので、その人の1回目と2回目、3回目と4回目の記録を組にすると、在室した半開区間の列 が得られる。各列は時刻順で、同じ人の区間同士は重ならない。人数 と記録数 に大小関係はなく、一度も入室しない人の列は空になる。
二人の答えは、二つの区間列の共通部分の長さの合計である。現在見ている区間を とすると、足す長さは
となる。その後、右端の早い区間のポインタを進める。同じ右端なら両方を進めてよい。これで二列の長さの和に比例する時間で答えられるが、区間の多い二人を繰り返し質問されると、1質問あたり 、全体で になりうる。逆に、質問されない組も含めて全員の組を前計算すると、 個の表が必要になる。
そこで正整数の閾値 を設け、 の人を light、それより多い人を heavy と呼ぶ。両者が light なら上の走査は で済む。一方、heavy の人数を とすると、区間の総数はちょうど だから
である。人数からではなく、各 heavy が少なくとも 個の区間を消費することから上界を得る。
本解説では、各 heavy と 人全員の答えを、長さ の配列1行として保存する。表を と書き、heavy の人番号から行番号を引く配列も持つ。この方式なら heavy を含む質問は表の1要素を読むだけになる。以下の計算量では、記録に現れない人の分も含む配列の初期化・保存を数える。
heavy の一人と全員の答えを求める
heavy の人 を固定する。 が入退室するたびに、その時点の全在室者を更新すると再び遅くなる。代わりに、相手の在室区間の端点だけで答えを求められないかを考える。
を「時刻 から までに が在室していた時間の合計」と定義する。これは が在室中だけ進む専用の時計である。相手 が に在室したなら、その間に時計が進んだ量
が、二人の同時在室時間になる。例えば が 、 が に在室した場合、 なので差は4である。 の入退室時に が不在でも、間の出入りが時計へ反映される。
この時計を全記録の時刻順の走査で計算する。各人の在室フラグ、入室時の時計の値を保存する配列、回答表の今回の行を0で初期化し、時計の値と直前時刻も0にする。各記録 では次の順に処理する。
- 直前の記録から今の時刻まで が在室していたなら、その時間差を時計へ足す。直前時刻を に更新する。
- の入室なら現在の時計を保存する。退室なら、現在の時計から保存した値を引いて へ足す。
- の在室フラグを反転する。 のときも、時計を進め終えてから反転する。
1記録あたり定数時間で、全記録を走査すると1行が完成する。ただし長さ の行と作業用配列の初期化もあるため、heavy 一人の費用は である。完成した行は表に残し、作業用配列は次の heavy に再利用する。
全質問は先に読み、 を見て閾値を決める。人別の区間列を作って heavy を分類し、全 heavy の行を前計算したら、質問ごとに heavy の側の行を参照する。どちらも light なら二つの区間列を走査する。質問の番号の大小によって heavy 側が決まるわけではなく、両方が heavy ならどちらの行でもよい。
典型の発動条件
sqrt decompositionによるheavy-light分類
要素ごとの出現数が偏り、二者間の質問を多数処理するときに使える。軽い組はその場で処理し、重い要素だけ一括前計算する。重い要素の数は、分類に使った量の総和から評価する。さらに「一人あたり全記録を読む費用」と「全員分の配列を作る費用」の両方を掛ける。
sorted区間列のintersection
互いに重ならず時刻順に並んだ二つの区間列なら、右端の早い側を進めるだけで共通部分の長さを求められる。一方の区間数だけではなく、両列の長さの和が走査回数の上界になる。
問題固有の要素
各人の記録数が偶数で、全員が最初も最後も室外にいるため、全区間数を正確に と数えられる。また、heavy 専用の累積在室時間を作れば、相手の入退室端点での差だけで交差長を集計できる。この二点が、heavy の人数と一行の計算費用をそれぞれ抑えている。
この方式では記録のない人も表の列を占める。閾値を固定の平方根で決める前に、時間の二項に加えて「何行を何人分保存するか」を数える必要がある。
正当性
は、 が在室している時間だけ増える。時刻差を加えてからフラグを反転するので、各記録の処理時に持つ時計の値は と一致する。したがって相手の在室区間 について、入室時に保存した値を退室時の値から引くと、区間内で も在室していた時間をちょうど得る。相手の区間は互いに重ならないので、その差の総和が表の答えになる。記録のない相手の値は初期値0のままで正しい。
light 同士の走査では、現在の二区間の交差を足した後、右端の早い区間を捨てる。その区間の右端は、相手の次の区間の左端以下なので、相手の未処理区間との交差は残っていない。従って交差を漏れなく重複なく数え、片方の列が尽きた時点で終了できる。端点が接するだけなら交差長は0である。
以上の二方式はともに二人の在室区間の交差長の総和を返す。閾値による分類は処理方法だけを変えるので、heavy の有無に応じた回答はすべて正しい。
実装上の注意
- 人別の記録を隣接する組にして半開区間を作る。全体の記録は既に時刻順なので、並べ直す必要はない。空の区間列なら共通時間は0である。
- heavy ごとの走査では時計・在室フラグ・入室時の時計を初期化する。時計を進める前に のフラグを反転すると、入室前や退室後の時間を加えてしまう。
- 回答表は heavy の行番号と人番号で直接参照できる配列にする。本解説では連想配列への挿入・検索や、同じ質問の答えを追加で保存する処理を使わない。
- 時間と回答は64 bit整数で持つ。回答表の要素数や保持 bytes の積も、配列を確保する前に十分な整数幅で計算する。
復習の核
- heavy の人数は、全人数ではなく分類に使った量の総和から導く。今回は一つの区間に入室・退室の2記録が必要である。
- 「全記録を1回走査」で終わらず、前後の配列初期化と回答表の保持まで数える。記録数と人数に大小関係がない点に注意する。
- 共通時間は、一人の在室中だけ進む時計の端点差で取り出せる。途中の出入りのたびに全相手を更新しなくてよい。
計算量と制約
時間
全体は、実際の heavy 人数 を用いて
となる。人別の空の区間列や heavy 判定用配列の準備・全員の分類に 、記録の変換に 、質問の入出力に かかる。heavy 一人につき長さ の配列を初期化して 記録を走査するので 、light 同士の質問は1件 である。よって人数の上界を代入すると
とも書ける。今回は全員分の表を持つので、 が 以下とは限らない入力に対して、heavy 前計算を とだけ評価することはできない。
空間
である。 人分の区間列の管理領域と作業用配列、 件の記録と計 個の区間、 件の質問、 要素の回答表を保持する。各行を表の保存先で直接作り、heavy ごとの作業用配列は使い回す。heavy が0人でも の固定費用は残る。
制約との対応
公式制約は 、、。各人の記録数は偶数で、質問の二人は異なる。制限は5秒・1024 MiBである。
閾値は、時間の二項 と を釣り合わせると、定数倍を除く目安として
を得る。 の整数へ調整する。 なら全員が light になる。次に実際の を数え、64 bit整数の表だけで bytes 必要なことを確認する。メモリが足りなければ を大きくして行数を減らし、増える light 側の走査も評価し直す。
例えば上限の では、上の目安は約632である。近い規模の整数として を採ると、 なので、表は最大39,800,000要素、318,400,000 bytes(約303.7 MiB)になる。記録・区間・質問・作業用配列も配列で持てば、それらの線形領域を加えて1024 MiB以内に収められる。
heavy 側の全記録走査は最大39,800,000件で、これに行の初期化などが加わる。light の質問は1件につき高々 回のポインタ前進、全質問で高々約2億回である。時間はこの走査と配列操作の実装定数にも左右されるため、連続配列で処理する。
具体的には とすれば、記録が少ない場合は全員を light にしつつ、全制約でこの人数・容量・走査回数の上界を満たせる。この選択を出発点に、上の時間式と実際の表の容量から閾値を調整してもよい。
例えば で一人しか記録に現れなくても、空の区間列や分類用配列を用意する費用は消えない。 なら heavy は0人で、全体は になる。一度も記録に現れない人を含む質問も、空の列から0と答えられる。
出典