event順にactive集合を更新する

概要

event・値順のオフライン走査

値・時刻・座標順にeventを並べ、同値eventの処理順を定めてactive集合や集約を増分更新する。

考え方

時刻・座標・閾値の順にeventを並べ、現在有効な集合だけを更新する。二次元の条件の一方を走査順で満たし、残る条件をデータ構造のqueryへ移す。

閉区間ではなく半開区間[l,r)のactive数を持つ例なら、lに+1、rに−1のeventを作り同座標をまとめる。座標xの差分を全て適用した後のactiveが[x,nextX)の数となる。その区間の長さnextX−xを掛ければ被覆長や積分を求められる。端点xへの包含queryもこの更新後に処理すれば、始点は含み終点は除く規約と一致する。

狭義不等号a_j<a_iを守るDPの同値batchでは、a_iの全queryを済ませてからbatchの全updateを行う。広義≤なら自身を含めてよいかまで確認して順を定める。同値eventをsortの偶然の順序で処理せず、状態が「現在座標の直前・直後」のどちらを表すかを不変量にする。

成立条件と計算量

event数Eならsort O(E log E)と更新・queryの総費用。同値eventで「追加→query→削除」のどれを先にするかは開閉境界から決める。圧縮座標の順位と実距離を混同しない。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。時刻・座標で整列し、同時eventの順序とactive集合の不変量を保つ。

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

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-event-sweep

習得する技能

  • 値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: kinetic sorting・交差event順序更新。

値・時刻・座標順にeventを並べ、同値eventの処理順を決めてactive集合を増分更新する。逆向き処理や寄与分解とは不変量が異なるため独立に学ぶ。

このUnitでは扱わないもの

  • 更新を単に逆順へ読む処理、答えの局所寄与だけを集計する順序交換、sort-uniqueしたkeyの添字化、および固定方向の単純scan。

根拠