ABC 306 F — Merge Sets

考察

f(S_i,S_j)は各x∈S_iについてS_i∪S_j内のx以下の要素数を足したもので、S_i自身からの寄与は常に1+…+Mである。

残るcross termはi<jかつy∈S_j, y≤x∈S_iとなるordered element pairsの個数である。

棄却する候補: 各set pairをmerge-sortしてS_i elementsのranksを足す。

N^2 pairsがありN=10^4では重すぎる。

採用する候補: iをNから1へ走査し、後続setsの全valuesをFenwick treeへ入れて各A_{i,k}以下の個数をqueryする。

rank-sum definitionをconstant self ranksとcross inversionsへ分解し、set index逆走査のFenwick prefix countsで集計する。

典型の発動条件

式変形によるpair contribution化

発動条件: set merge後のrank和を全set pairsについて求め、自己寄与と他集合寄与へ分けられるとき。

各S_i要素以下のS_j要素数というcross comparisonへ展開する。

Fenwick treeのoffline走査

発動条件: index順条件i<jとvalue順条件y≤xを同時に満たすpairsを数えたいとき。

indexを逆走査してj>iだけをdata structureへ保持し、compressed value prefixをqueryする。

問題固有の要素

S_i内で各要素のrankは1,…,Mを一度ずつ取るため、値の並びに依らずself contributionはM(M+1)/2である。

別の問題へ持ち帰る視点: rank aggregateは同一group内の固定項を閉形式にし、group間比較だけをdata structureへ残す。

正当性

全valuesがdistinctなのでcoordinate compression後のprefix countが≤比較の個数にそのまま一致する。 within-set constant contributionはC(M+1,2)×C(N,2)として先に加え、Fenwickは他set由来だけを担当する。 全NM elementsについて一回のqueryと一回のinsertだけでcross termを数えられる。

実装上の注意

  • set iのqueriesをすべて終えてからそのM valuesをinsertし、同じsetをcross termへ混ぜない。
  • 答えはN^2M^2規模になり得るため64 bit整数を使う。

復習の核

  • rankの定義を「自分以下の要素数」に展開し、各ordered pairの寄与として読み替える。
  • indexとvalueの二条件を持つpair countingは、一方をscan順、他方をFenwick軸に割り当てる。

計算量と制約

時間

O(NM log(NM))、全値圧縮とFenwick。

空間

O(NM)。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 10^4; 1\leq M \leq 10^2; 1\leq A_{i,j} \leq 10^9; If i_1 \neq i_2 or j_1 \neq j_2, then A_{i_1,j_1} \neq A_{i_2,j_2}.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Merge Sets の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 寄与の数え上げと順序交換

    補助タグ: 座標・値の順序保存圧縮 event・値順のオフライン走査 Fenwick Tree・反転数・重み付き接頭辞統計

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

    学習の位置

    体系上の位置: 局所寄与へ分解して集計順を交換する

    • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

    先に読む単元:

    この解説で扱わないこと:

    • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題