ABC 292 Ex — Rating Estimator

考察

更新後の値a_iからq_i=a_i−Bを作る。平均が初めてB以上になる位置は、非空prefix和が初めて0以上になる位置sである。存在しなければs=N。求めるratingはB+(Σ_{i≤s}q_i)/sである。

各区間に(sum,maxPrefix)を持たせ、maxPrefixは非空prefixだけを対象とする。葉は(q_i,q_i)、空区間の単位元は(0,−∞)。S,Tの結合は(sumS+sumT,max(maxPrefixS,sumS+maxPrefixT))となる。

max_rightの判定を「maxPrefix<0」とする。単位元では真で、区間を右へ伸ばすとmaxPrefixは減らないため、最初の失敗位置を木上で探索できる。戻り値がrなら、r<Nの場合s=r+1、r=Nならs=N。区間[0,s)のsumからratingを求める。一点更新・探索・区間和は各O(log N)。空prefixの和0を最大に含めると、全ての探索が冒頭で失敗するので定義を区別する。

典型の発動条件

prefix最大モノイド

発動条件: 更新列で閾値を初めて越えるprefixを探す。

区間和と最大prefix和を結合してsegment treeに載せる。

segment tree上の二分探索

発動条件: prefix判定が単調に失敗する最初の位置が欲しい。

左から節点を降りてsを求める。

問題固有の要素

平均条件をp_i-Bの符号付き累積和へ移すと、動的な最初の閾値越えになる。

別の問題へ持ち帰る視点: 動的平均条件は基準値を各項から引いてprefix問題へ変換する。

正当性

Σ_{i≤s}(a_i−B)≥0はprefix平均≥Bと同値。区間の非空prefixはSだけに入るか、S全体とTの非空prefixからなるので結合式が成立する。maxPrefixは区間を伸ばすと単調非減少であり、最初に0以上となる境界をmax_rightで得られる。非空prefixが一つも該当しなければ問題の規則通り全N項を使う。

実装上の注意

  • 非負prefixが無い場合はs=Nとし、葉・単位元のmaxPrefix定義を空区間と混同しない。

復習の核

  • 直接prefix走査と照合し、最初の要素で到達・最後まで負・更新でsが左右へ動く例を確認する。

計算量と制約

時間

O(N+Q log N)、木上探索で最初の非負prefixを得る。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 5 \times 10^5; 1 \leq B \leq 10^9; 1 \leq Q \leq 10^5; 0 \leq a_i \leq 10^9; 1 \leq c \leq N; 0 \leq x \leq 10^9; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Rating Estimator の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間monoid要約

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

      主タグ: 区間monoid要約

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

      学習の位置

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題