みんなのプロコン 2017 予選 D

みんなになれなかった。

問題概要

読んで: D: 工場 - 「みんなのプロコン」 | AtCoder

解法

正攻法はそのままこのクエリを実現しようとすれば結合則成り立つので値を2,3個持ってくださいというやつみたいです(たしかにね。)。

クエリの時系列と日数の時系列の2次元なので、こういう時はとりあえず日数の時系列でクエリをソートして、segment treeのインデックスをクエリのインデックスにすることを考える。

D = D1, D2, ... , Dqを順に代入しつつ以下の値を考える(ただしD1 ~ Dqは昇順にソートしたクエリの日付)。

num[qidx] := qidx番目までのクエリを考慮した時、D日目までに販売した賞品の数

これをセグ木によって持つことを考える。

Dqidx = Dとなるようなqidx番目のクエリを処理することを考える。

経理質問(回答クエリ)については、num[qidx]を答えられれば良いので、この値をセグ木で実現できるなら特に考える必要がない。

注文追加(更新クエリ)について考える。

qidx番目のクエリによる更新が反映されるべきなのは、num[qidx] ~ num[Q]であって、それぞれのi ∈ [qidx, Q]について、num[i] = max(num[i]+Aqidx, K*D)という更新を行う。

K*DとAqidxは定数でnum[i]はiについて流石に単調増加なので、num[t] > K*D-Aqidxなる最小のtを二分探索で見つければ、t未満のインデックスについては区間に対してAを加算、t以上のインデックスについては区間に対してK*Dを代入をすればよく、これは、seg木にnum[i]の代わりにnum[i]-num[i-1]をもたせれば、Lazy Propagationによる区間代入をサポートした、区間和を求めるseg木によって実現できるので解ける。めちゃくちゃバグる。