概要
解法
- scorched：時刻 $T$ のイベント終了後の時点で、肉がグリルに置かれている
- underdone：時刻 $T$ のイベント終了直前の時点で、肉がグリルに残っていない
という事象なので、各肉が指定した時刻 $T$ でまだグリルに置かれている確率を求めればよいです。時刻 $S$ に置かれた肉が時刻 $T$ でもグリルに残っていることは、$[S,T)$ 間のすべての回収を回避することと同値です。
$t\in [S,T)$ で肉が $n_t$ 枚置かれているところから回収するとすると、その回収を回避する確率は $p_t:=1 – 1/n_t$ です。
したがって、時刻 $S$ に置かれた肉の時刻 $T$ までの生存確率は、$\prod_{t\in [S,T)} p_t$ と計算できます。
時刻を座標圧縮したあと、各回収時刻 $t$ に対して $p_t$ をのせたセグメント木を用いればこれを計算することができます。
- 時刻に対してデータを持たせる場合、ある時刻のイベントの前後のどちらなのかをはっきり定義して正確に処理するように意識すると良いと思います。
- セグメント木を用いると、引き算・除算の類が生じません。$p_t = 0$ である場合があるので、累積積あるいは $\log p_t$ の累積和を用いるのは少し難しいと思います（$\log$ でをとって、$\log 0$ の類を上手く別に扱えば正しく解くことは可能だと思います。）。
