ABC 306 E — Best Performances

考察

上位の要素を毎回並べ直す代わりに、「和に含める側」と「残り」に分けておく。一つの値が変わったとき、選び直す必要があるのは二つの集合の境界付近だけである。境界を修復すると同時に和を更新すれば、毎回上位の全要素を足し直す必要もない。

各更新の後で数列全体をソートする方法では、N,Q≤5×105N,Q\leq 5\times 10^5 に対して O(QNlog⁡N)O(QN\log N) 時間がかかる。一方、答えに必要なのは上位 KK 個の和であり、上位の内部での順位までは必要ない。そこで、重複を許す順序付き集合である multiset を二つ使い、値を次のように分ける。

  • XX:和に含める上位 KK 個の値。
  • YY:それ以外の値。
  • ss:XX に含まれる値の総和。

保つべき条件は、∣X∣=K|X|=K というサイズの条件と、両集合が空でないときの min⁡(X)≥max⁡(Y)\min(X)\geq\max(Y) という順序の条件である。後者は、選んだ側の最小値さえ残りの最大値以上であることを表す。この二条件があれば XX は上位 KK 個になり、答えは ss でよい。

最初の数列はすべて 00 なので、XX に KK 個、YY に N−KN-K 個の 00 を挿入し、s=0s=0 とする。配列 AA も別に保持し、更新される位置の旧値を取り出せるようにする。集合には位置を持たせず、値とその個数を管理する。

二条件を回復する操作を balance とし、次の順で行う。移動・交換では、対象の値を一個ずつ取り扱う。

  1. ∣X∣<K|X|<K の間、YY の最大値 bb を XX へ移し、ss に bb を足す。
  2. 両集合が空でなく、a=min⁡(X)<b=max⁡(Y)a=\min(X)<b=\max(Y) である間、aa と bb を交換し、ss に b−ab-a を足す。

この後で定義する追加・削除では ∣X∣>K|X|>K にはならない。サイズ超過も起こる別の規則へ拡張するなら、不足を補う前に XX の最小値を YY へ移して ss から引き、サイズを KK まで減らせばよい。

サイズが合うだけでは不十分である。例えば K=2K=2、X={5,3},Y={2,1},s=8X=\{5,3\},Y=\{2,1\},s=8 から、値 11 を 1010 へ変える場合を考える。新値 1010 を YY に入れても ∣X∣=2|X|=2 のままだが、min⁡(X)=3<10=max⁡(Y)\min(X)=3<10=\max(Y) なので上位二個にはなっていない。33 と 1010 を交換して s=8+(10−3)=15s=8+(10-3)=15 とし、その後 YY に残る旧値 11 を消せば、X={10,5},Y={3,2}X=\{10,5\},Y=\{3,2\} となる。

位置 pp の値を vv に変える更新は、旧値 u=Apu=A_p を保存してから、次の手順で処理する。

  1. add(v):vv をまず YY に一個追加し、balance する。
  2. erase(u):XX に uu があれば一個削除して ss から uu を引く。なければ YY から一個削除する。その後 balance する。
  3. Ap=vA_p=v とし、ss を出力する。

新値を先に入れるため、balance を呼ぶ時点の総要素数は一時的に N+1N+1 個、その後 NN 個となり、常に KK 個以上ある。したがって不足を補う間は YY が空にならない。旧値を先に消すと、K=NK=N の場合に総要素数が K−1K-1 個になり、同じ補充手順を使えない。新旧の値が等しくても、値を一個足して一個消すという処理でよい。

典型の発動条件

二つのmultisetによるtop-K維持

一要素ずつ値が変わり、そのたびに固定した個数の上位または下位の値を集計したいときに使う。選ぶ側と残す側を分け、サイズと境界の大小関係をそれぞれ保つ。基本単元の「小さい kk 個の和」とは大小が逆であり、本問では選ぶ側の最小値と残りの最大値を比較する。KK 自体を一度に大きく変える問題では移動数も増えるため、一更新が同じ計算量になるとは限らない。

選択集合のrunning aggregate

選んだ集合への出入りを追えるなら、和は要素の追加・削除・交換と同時に差分更新できる。本問では XX に入る値を足し、出る値を引くことで、集合全体の走査を省く。二集合の分割が正しくても、和の更新を一つ忘れると答えは一致しない。

問題固有の要素

初期値がすべて 00 なので、最初にどの位置を上位側へ置くかを決める必要はない。KK 個と N−KN-K 個に分けるだけで二条件を満たす。また、同じ値ならどの位置の要素も和への寄与は等しいため、集合内で位置を識別せず旧値を一個消してよい。位置と値の対応は配列 AA が受け持つ。

正当性

初期状態では二集合を合わせた値と個数が数列に一致し、サイズと順序の条件も満たす。add(v) と erase(u) は値をそれぞれ一個追加・削除し、balance は所属だけを変えるため、更新後の二集合を合わせると、旧値一個を新値一個に置き換えた数列と一致する。同値が両集合にあっても、どちらから消すかによって残る値の個数は変わらない。

追加前に二条件が成立しているとする。新値は YY に入るので ∣X∣=K|X|=K は変わらず、順序を壊す可能性があるのは新値だけである。新値が min⁡(X)\min(X) 以下なら交換は不要である。より大きいなら、新値は YY の最大値になるため、XX の最小値と一回交換する。交換後の XX の各値は交換前の最小値以上、YY の各値はそれ以下となり、順序も回復する。

続く削除では、YY から消すならサイズも順序も保たれる。XX から消すなら一個だけ不足するが、削除自体は残った要素の大小関係を壊さない。YY の最大値を一個補充すると、もともと XX に残った値は補充値以上であり、補充値は YY に残る値以上である。よってサイズと順序がともに回復する。K≥1K\geq 1 かつ総要素数が KK 以上なので補充は可能であり、XX が一時的に空になる場合にもこの議論は成り立つ。

ss は初期値が XX の和と一致し、XX への追加・削除・交換ごとに出入りした値だけを加減するので、常にその和に一致する。各更新の最後には XX がちょうど KK 個で、どの値も YY の値以上である。したがって ss は求める上位 KK 個の和になる。また、一更新の修復は追加時の交換高々一回と削除時の補充高々一回で済む。

実装上の注意

  • multiset は重複を保持する。C++ の erase(value) は同じ値をすべて消すので、find で得たイテレータを erase に渡して一個だけ消す。XX で見つからなければ YY を探す。新旧が同値のときも、個数を一個ずつ扱う。
  • 順序の比較は、両集合が空でないことを確認してから行う。K=NK=N では更新完了時に YY が空になる。K=1K=1 では XX から削除した直後に XX が空になるが、先に不足を補ってから境界を比較すればよい。N=K=1N=K=1 もこの手順に含まれる。
  • 和は最大 K×109≤5×1014K\times 10^9\leq 5\times 10^{14} になるため、ss は64 bit整数で保持する。

復習の核

  • 上位・下位の固定個数を保つなら、「選ぶ個数」と「境界の大小関係」を別々の不変条件にする。サイズだけでは選び方の正しさを保証できない。
  • 追加先を決めたら、壊れる条件と修復に必要な移動数まで追う。新値を先に足すと、上位全要素を選ぶ場合でも補充元を確保できる。
  • 選択集合の和は、所属が変わる瞬間に更新する。同値の削除は一個だけにする。

計算量と制約

時間

初期値の 00 を通常の multiset 挿入で合計 NN 回入れるため、初期化は O(Nlog⁡(N+1))O(N\log(N+1)) 時間とする。一更新では検索・挿入・削除に加え、境界交換と不足の補充がそれぞれ高々一回であり、O(log⁡(N+1))O(\log(N+1)) 時間で処理できる。出力まで含めた全体は O((N+Q)log⁡(N+1))O((N+Q)\log(N+1)) 時間。N=1N=1 も含めるため、対数を log⁡(N+1)\log(N+1) と表記している。

空間

配列 AA に NN 個、二つの multiset に合計で最大 N+1N+1 個の値を保持する。更新を一件ずつ読み、答えを順次出力すれば、空間計算量は O(N)O(N)。

制約との対応

1≤K≤N≤5×1051\leq K\leq N\leq 5\times 10^5、1≤Q≤5×1051\leq Q\leq 5\times 10^5。各更新は一つの位置を指定し、新値は 00 以上 10910^9 以下の整数である。全体を毎回ソートする代わりに、一更新につき定数回の平衡木操作へ絞る。時間制限は6秒、メモリ制限は1024 MiB。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Best Performances の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題