座標・値の順序保存圧縮
疎な初期値・将来更新値・event座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写す。
この典型を扱う単元: 疎なkeyの順序を保ってdense indexへ圧縮する
検索別名: coordinate compression、rank compression、値圧縮、座標圧縮
未知問からこの典型を見つける手掛かり
- 扱う対象
- key
- 値
- 座標
- 更新値
- 疎な状態
- 使う手掛かり
- sort
- unique
- 大小関係だけ
- 将来のqueryを先読み
- 保つ不変量
- dense index
- 有限候補
- 等値性を保つ
- 順序を保つ
- 求めるもの
- Fenwick Tree
- Segment Tree
- 有限状態化
- 配列添字化
- 適用しない条件
- linear scan only
- 単純scanだけ
- 固定.*方向.*scanだけ
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
- event・値順のオフライン走査: 順序付きeventに沿ってactive状態を更新する走査と、順序・等値性だけを保って添字化する圧縮を区別する。
- event・値順のオフライン走査: 疎なevent座標を圧縮してFenwick TreeやSegment Tree上でactive情報を更新する構成で頻繁に併用する。
- Fenwick Tree・反転数・重み付き接頭辞統計: 疎な値を順序保存圧縮してから、個数・重み・反転数をprefix集約する構成で併用する。
学習成果と学習単位
初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。
疎なkeyの順序を保ってdense indexへ圧縮するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC221 E「LEQ」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 寄与の数え上げと順序交換、座標・値の順序保存圧縮、法上の四則演算・高速累乗・逆元
- ABC287 G「Balance Update Query」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
- ABC351 F「Double Sum」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 座標・値の順序保存圧縮、event・値順のオフライン走査
- ABC374 F「Shipping」 公式問題主題: prefix分割DP / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC221 E「LEQ」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 寄与の数え上げと順序交換、座標・値の順序保存圧縮、法上の四則演算・高速累乗・逆元
- ABC231 F「Jealous Two」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC232 G「Modulo Shortest Path」 公式問題主題: 最短路モデル / 補助タグ
- ABC254 G「Elevators」 公式問題主題: doubling・binary lifting / 補助タグ
- ABC262 Ex「Max Limited Sequence」 公式問題主題: prefix分割DP / 補助タグ
- ABC266 Ex「Snuke Panic (2D)」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC273 F「Hammer 2」 公式問題主題: 区間拡張DP / 補助タグ
- ABC276 Ex「Construct a Matrix」 公式問題主題: 線形方程式・rank / 補助タグ
- ABC287 G「Balance Update Query」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
- ABC306 F「Merge Sets」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC309 F「Box in Box」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC320 G「Slot Strategy 2 (Hard)」 公式問題主題: 二部matching・Hall・Kőnig / 補助タグ
技能・出典
主タグ: 二部matching・Hall・Kőnig / 補助タグ: 座標・値の順序保存圧縮、貪欲法と交換論、剰余周期・指数法則、単調境界探索
- ABC351 F「Double Sum」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 補助タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 座標・値の順序保存圧縮、event・値順のオフライン走査
- ABC354 F「Useless for LIS」 公式問題主題: 値域集約による部分列DP / 補助タグ
- ABC356 F「Distance Component Size Query」 公式問題主題: ordered set・multisetの動的順序管理 / 補助タグ
- ABC360 F「InterSections」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC360 G「Suitable Edit for LIS」 公式問題主題: 値域集約による部分列DP / 補助タグ
- ABC374 F「Shipping」 公式問題主題: prefix分割DP / 補助タグ
- ABC384 G「Abs Sum」 公式問題主題: Moの順序で区間問い合わせの差分を更新する / 補助タグ
技能・出典
主タグ: Mo's algorithmによるオフライン区間問い合わせ / 補助タグ: 座標・値の順序保存圧縮、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC431 G「One Time Swap 2」 公式問題主題: ordered set・multisetの動的順序管理 / 補助タグ
- ABC434 E「Distribute Bunnies」 公式問題主題: DSUによる連結成分管理・縮約 / 補助タグ
- ABC439 F「Beautiful Kadomatsu」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元
- ABC465 G「Sum of Mex of Mod of Linear」 公式問題主題: 端点更新型のrun分割管理 / 補助タグ