event・値順のオフライン走査
値・時刻・座標順にeventを並べ、同値eventの処理順を定めてactive集合や集約を増分更新する。
この典型を扱う単元: event順にactive集合を更新する
検索別名: event sweep、sweep line、イベント走査、走査線
未知問からこの典型を見つける手掛かり
- 扱う対象
- event
- threshold
- 値
- 区間
- 時刻
- 使う手掛かり
- activate
- deactivate
- sort
- sweep
- ソート
- 保つ不変量
- active
- 処理済み境界
- 同値eventの順序
- 求めるもの
- 全体
- 区間
- 同時
- 面積
- 適用しない条件
- sort.?uniqueだけ
- 単純scanだけ
- 固定.*方向.*scanだけ
- 座標圧縮だけ
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
- 座標・値の順序保存圧縮: 順序付きeventに沿ってactive状態を更新する走査と、順序・等値性だけを保って添字化する圧縮を区別する。
- 座標・値の順序保存圧縮: 疎なevent座標を圧縮してFenwick TreeやSegment Tree上でactive情報を更新する構成で頻繁に併用する。
- 方向別grid scanによる長距離効果の前計算: 順序に沿って進みながら少数のactive状態だけを更新する発想は共通する。一方、固定方向scanにはeventのsort・追加・削除がなく、event sweepそのものとは区別する。
- ordered set・multisetの動的順序管理: eventの追加・削除に応じてactive候補の最小値・近傍・順位を動的に保つ構成で併用する。
学習成果と学習単位
値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。
event順にactive集合を更新するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC320 E「Somen Nagashi」 公式問題主題: event順にactive集合を更新する / 主タグ
技能・出典
主タグ: event・値順のオフライン走査 / 補助タグ: ordered set・multisetの動的順序管理、priority queue・best-first列挙
- ABC231 F「Jealous Two」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC346 G「Alone」 公式問題主題: event順にactive集合を更新する / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC214 E「Packing Under Range Regulations」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC223 H「Xor Query」 公式問題主題: XOR線形基底 / 補助タグ
- ABC224 E「Integers on Grid」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC231 F「Jealous Two」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC233 Ex「Manhattan Christmas Tree」 公式問題主題: parallel binary search・多数境界の判定共有 / 補助タグ
- ABC235 E「MST + 1」 公式問題主題: Kruskal順の閾値DSU sweep / 補助タグ
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP / 補助タグ
技能・出典
主題: 値域集約による部分列DP
主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC245 E「Wrapping Chocolate」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC250 Ex「Trespassing Takahashi」 公式問題主題: Kruskal順の閾値DSU sweep / 補助タグ
技能・出典
主タグ: Kruskal順の閾値DSU sweep、最短路モデル / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC254 G「Elevators」 公式問題主題: doubling・binary lifting / 補助タグ
- ABC263 Ex「Intersection 2」 公式問題主題: 単調境界を証明して探索する / 補助タグ
技能・出典
主題: 単調境界を証明して探索する
主タグ: 単調境界探索 / 補助タグ: 円環順序・chord交差、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換
- ABC266 Ex「Snuke Panic (2D)」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC268 Ex「Taboo」 公式問題主題: 接尾辞の順序とLCPを索引化する / 補助タグ
技能・出典
主題: 接尾辞の順序とLCPを索引化する
主タグ: 接尾辞順序・LCP索引 / 補助タグ: event・値順のオフライン走査、貪欲法と交換論、ordered set・multisetの動的順序管理、区間monoid要約
- ABC274 F「Fishing」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC280 G「Do Use Hexagon Grid 2」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC283 F「Permutation Distance」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC287 Ex「Directed Graph and Query」 公式問題主題: 推移閉包 / 補助タグ
- ABC296 G「Polygon and Points」 公式問題主題: 幾何の基本判定と座標変換 / 補助タグ
- ABC301 Ex「Difference of Distance」 公式問題主題: lowlinkで橋・関節点を特定する / 補助タグ
技能・出典
主タグ: Kruskal順の閾値DSU sweep、lowlinkによる橋・関節点の検出 / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC306 F「Merge Sets」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC308 F「Vouchers」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC309 F「Box in Box」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC311 G「One More Grid Task」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC320 E「Somen Nagashi」 公式問題主題: event順にactive集合を更新する / 主タグ
技能・出典
主タグ: event・値順のオフライン走査 / 補助タグ: ordered set・multisetの動的順序管理、priority queue・best-first列挙
- ABC327 F「Apples」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC332 G「Not Too Many Balls」 公式問題主題: 最大流・最小カット / 補助タグ
- ABC337 G「Tree Inversion」 公式問題主題: Euler順による部分木区間化 / 補助タグ
- ABC344 G「Points and Comparison」 公式問題主題: kinetic sorting・交差event順序更新 / 補助タグ
- ABC346 G「Alone」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC351 F「Double Sum」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 座標・値の順序保存圧縮、event・値順のオフライン走査
- ABC360 F「InterSections」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC361 G「Go Territory」 公式問題主題: 状態グラフのモデリングと探索 / 補助タグ
- ABC363 E「Sinking Land」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC368 E「Train Delay」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC393 F「Prefix LIS Query」 公式問題主題: LIS・末尾の支配関係 / 補助タグ
- ABC394 G「Dense Buildings」 公式問題主題: parallel binary search・多数境界の判定共有 / 補助タグ
- ABC401 E「Reachable Set」 公式問題主題: DSUによる連結成分管理・縮約 / 補助タグ
- ABC407 F「Sums of Sliding Window Maximum」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: event・値順のオフライン走査、ordered set・multisetの動的順序管理、累積和・差分配列
- ABC408 F「Athletic」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC410 G「Longest Chord Chain」 公式問題主題: 値域集約による部分列DP / 補助タグ
- ABC411 E「E [max]」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換、法上の動的積・剰余 0 因子の分離 / 補助タグ: event・値順のオフライン走査、法上の四則演算・高速累乗・逆元
- ABC431 G「One Time Swap 2」 公式問題主題: ordered set・multisetの動的順序管理 / 補助タグ
- ABC433 E「Max Matrix 2」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC436 F「Starry Landscape Photo」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC438 G「Sum of Min」 公式問題主題: gcd不変量・差分構造 / 補助タグ
- ABC447 G「Div. 1 & Div. 2」 公式問題主題: 区間monoid要約 / 補助タグ
- ABC449 E「A += v」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC449 F「Grid Clipping」 公式問題主題: event順にactive集合を更新する / 主タグ
- ABC453 E「Team Division」 公式問題主題: event順にactive集合を更新する / 主タグ