Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 221 D問題 Online games

AtCoder ABC ABC221 D問題 400 pts

問題

提出解答

問題の概要

あるオンラインゲームは $N$ 人のプレイヤーがおり, $i~(1 \leq i \leq N)$ 番目のプレイヤーは $A_i$ 日目から $A_i+B_i-1$ 日目のみ全てログインしている. $k=1,2,\dots, N$ において, ちょうど $k$ 人がログインしている日数をそれぞれ求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i, B_i \leq 10^9$

解法

各日のそれぞれのログイン人数そのものではなく, 差分を求めることにする. $T_i$ で $i-1$ 日目と $i$ 日目のログイン人数の差分を表すとする (増えるならば, $T_i>0$ ).

$A_i$ 日目から $A_i+B_i-1$ 日まで連続でログインするということは,

$T_{A_i}$ は $1$ 増え
$T_{A_i+B_i}$ は $1$ 減る

この $T$ を利用し, $d$ 日目のログイン人数を $L_d$ とすると,

$\displaystyle L_d=\begin{cases} 0 & (d=0) \\ L_{d-1}+T_d & (d \geq 1) \end{cases}$

である. しかし, $T$ は高々 $2N$ 個以外は全て $0$ であることから, $T$ を辞書で記録し, $T_d \neq 0$ となる $d$ を昇順に列挙し, 飛ばした日数に注意して, $k$ 人がログインした日数を加算することにより, 計算量 $O(N \log N)$ で求めることができる.