ABC 281 E — Least Elements

考察

各windowのK個の最小値をmultiset L、残りをRとして持つ。|L|=Kかつmax(L)≤min(R)なら、答えはsum(L)である。slideでは新しい値を先にLまたはRへ挿入し、その後でwindowから出る値を削除する。この順ならK=1でも削除前にLが空にならず、挿入先を境界で判定できる。

挿入と削除の後、|L|がKと違えば境界の一要素を移して戻す。初windowを作り、各slideで二つの変更だけを処理すれば、全体sortを繰り返さずに済む。重複値があるため、値だけでなくindexを組にするか、該当する一個だけを消す。

典型の発動条件

two-multiset order statistics

発動条件: 動的multisetの小さい方K個と残りを分け、その集約値を維持したいとき。

境界maxL/minRとsizeを不変量にし、insert/erase後にrebalanceする。

sliding window差分更新

発動条件: 連続window間で出入りする要素が少数のとき。

outgoing削除とincoming挿入だけをdata structureへ反映する。

問題固有の要素

K-th値そのものではなくK最小値の和なので、balanced partitionにsum metadataを足すだけでqueryがO(1)になる。

別の問題へ持ち帰る視点: dynamic order statisticのprefix集約では、境界で集合を二分し片側のsum/countを持つ。

正当性

挿入時にmax(L)との比較で振り分けると順序条件は保たれ、削除後にサイズがKと一つだけずれた場合は境界要素の移動で|L|=Kへ戻る。よって各windowでLはちょうどK個の最小値を含み、保持したsum(L)が求める和になる。

実装上の注意

  • 新要素を先に挿入してからoutgoingを削除する。特にK=1で、空のLを参照して挿入先を決めないようにする。
  • rebalance後にsum(L)を出力する。重複値を消すときは一要素だけ削除し、K=MでRが空の分岐も扱う。
  • sum(L)は64 bit整数で保持する。

復習の核

  • 境界値が重複するwindowで同値要素がL/R両方にある例を作り、どちらから1個消しても不変量を戻せる実装を確認する。

計算量と制約

時間

O(M log M+(N−M)log M)、N列長、M窓長。

空間

O(M)、二multiset。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq K \leq M \leq N \leq 2 \times 10^5; 1 \leq A_i \leq 10^9; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Least Elements の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: ordered set・multisetの動的順序管理

主題
  • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: ordered set・multisetの動的順序管理

    補助タグ: 尺取り法・sliding window

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: ordered set・multisetの動的順序管理

    • 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題