Moの順序で区間問い合わせの差分を更新する

概要

Mo's algorithmによるオフライン区間問い合わせ

区間問い合わせを端点の移動量が小さい順に並べ、一要素の追加・削除で答えを更新する。

ABC242 Gでは値vの頻度f_vからΣ floor(f_v/2)を維持する。端の追加・削除では一つの頻度だけが変わるのでO(1)で差分更新できる。ABC293 Gでは同じ枠組みでΣ C(f_v,3)を保つ。まず端点操作を定義し、その後にquery順の並べ替えで総移動量を抑える。

ABC405 GではMoで現在区間を動かしながら、別の軸である値をbucketに分ける。値vの頻度が変わるたび所属bucketの頻度和と逆階乗積をO(1)で修正し、値prefix [1,X)の完全bucketと端数からk! / ∏ f_v!を求める。区間端の移動がO(N√Q)回、答えの取得がQ回なので、更新側からlog因子を外す効果が大きい。

Moはquery順の再配置、値bucketは座標軸のblock分割、heavy/lightは対象を頻度や次数で分類する技法である。平方根が現れるという共通点だけで同一視せず、何を分け、どの操作の総回数を減らしたかを説明する。

考え方

すべての区間queryを並べ替え、隣のqueryへ移る際の端点移動を少なくする。add/removeで現在区間の答えを保てれば、毎回最初から計算する必要がない。

query順と端点の更新規則

半開区間[l,r)を左端block floor(l/B)の昇順、同block内では右端rの昇順へsortする。blockごとに右端を逆順へ交互に変えると定数倍を抑えられる。現在区間[L,R)を空の[0,0)から始め、L>lならLを減らしてその要素をadd、R<rならRの要素をaddしてRを増やす。範囲を広げ終えてから、L<lならLをremoveして増やし、R>rならRを減らしてremoveする。全更新後の集約を元のquery IDへ保存する。

頻度f_vに対し答えがΣg(f_v)なら、addは ans+=g(f_v+1)−g(f_v)、removeは ans+=g(f_v−1)−g(f_v) として頻度も同時に変える。左端は同block内のquery間でO(B)、block切替え全体でO(N)、右端は一blockでO(N)動く。よってQ>0ではO(QB+N²/B+N)回の移動(Qが0なら走査しない)にsort O(Q log Q)と答え取得費用を加える。

成立条件と計算量

block幅Bなら端点移動は典型的にO(QB+N²/B)、一回の更新費用を掛ける。offlineと可逆な端点更新が前提。時間軸の更新を含むMoは状態と上界が変わる。removeが正しく逆操作になるか確認する。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。追加・削除可能な集計を作り、query順の変更で端点移動量を抑える。

対象色の読み方は本書の読み方を参照してください。

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-mo-offline-range

習得する技能

  • 区間問い合わせの順序と追加・削除操作を設計し、端点移動の総量を評価できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

区間への要素の追加・削除を定義し、問い合わせ順を並べ替えて端点移動の総量を抑える。

このUnitでは扱わないもの

  • オンラインのpriority queue・multiset、および単調stack・queue。

根拠