ABC 343 F — Second Largest Query

考察

区間を結合した時の最大・second distinct最大は、左右区間それぞれの上位二distinct値のどれかに限られる。したがって値と出現数のpairを二つだけ持つ情報がsegment treeのmonoidになる。

採用する候補: 各nodeに上位二distinct値と各countを持つsegment tree

棄却する候補: query区間を毎回sortまたはfrequency map化する

range長に比例し、Q回の最悪計算量がO(NQ)またはO(QN log N)になる。

木の位置i−1を公式のA_iへ対応させ、葉を(A_i,1,−∞,0)で初期化する。単位元は(−∞,0,−∞,0)。mergeではcount>0の高々4候補だけをvalue別に合算し、上位二distinct値を返す。タイプ1は位置p−1への代入、タイプ2の公式閉区間[l,r]はprod(l−1,r)へ写し、第二値のcountを出力する。第二値がなければ0。例えばA=(1,2,2)、質問[2,3]は全て2なので0、[1,3]は第二値1が一個なので1であり、左端や右端を落とすと区別できない。

典型の発動条件

top-k monoid

発動条件: range queryがdistinct値の上位k個と各frequencyだけを必要とし、kが定数である。

子nodeの候補2k個をmergeし上位kへtruncateするsummaryを持つ。

point update・range fold

発動条件: 配列一点代入と区間summary queryが混在する。

segment treeのleaf更新とassociative mergeで処理する。

問題固有の要素

単なる二番目の要素でなく二番目に大きいdistinct valueなので、同値候補は順位を消費せずcountを合算する必要がある。

別の問題へ持ち帰る視点: order statisticsのrange summaryでは重複の順位定義に応じてvalue統合とmultiplicityを分ける。

正当性

mergeでは左・右から最大4個の(value,count)候補を集め、同じvalueのcountを合算してdistinct value順の上位二つだけ残せばよい。この演算は区間multisetの要約なので結合順に依存せずassociativeである。 point assignmentとrange queryをどちらもO(log N)で処理し、query結果のsecond countを直接返せる。

実装上の注意

  • identityには実入力より小さいsentinelとcount 0を使い、sentinel同士を実候補として数えない。長さ1や全要素同値のqueryは0になる。

復習の核

  • 全同値、最大値だけ重複、second値が左右nodeに跨る、更新で順位が入れ替わる例をsort真値と比較する。

計算量と制約

時間

O(N+Q log N)。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N, Q \leq 2 \times 10^5; 1 \leq A_i \leq 10^9; For type-1 queries, 1 \leq p \leq N.; For type-1 queries, 1 \leq x \leq 10^9.; For type-2 queries, 1 \leq l \leq r \leq N.; There is at least one type-2 query.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Second Largest Query の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間monoid要約

主題
  • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 区間monoid要約

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

      学習の位置

      体系上の位置: 区間monoid要約

      • 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題