考察
区間を結合した時の最大・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.
出典