Kazun の競プロ記録

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

AtCoder Beginner Contest 294 D問題 Bank

AtCoder ABC294 ABC 400 pts D問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 人の人がいる. これらの人は人 $1$ , 人 $2$ , $\dots$ , 人 $N$ と名付けられている.

以下の $Q$ 個のイベントを順に処理せよ.

${\tt 1}$ 受付に呼ばれていない人のうち, 最も小さい番号の人が受付に呼ばれる.
${\tt 2~x}$ 人 $x$ が受付に行く. (この時点で人 $x$ はすでに $1$ 回以上受付に呼ばれている.)
${\tt 3}$ すでに受付に呼ばれているが受付に行っていない人のうち, 最も小さい番号の人が再度呼ばれる.

${\tt 3}$ のイベントにおいて, 呼ばれた人の番号を求めよ.

制約

$1 \leq N \leq 5 \times 10^5$
$2 \leq Q \leq 5 \times 10^5$
各イベントに対する制約
- ${\tt 1}$ : 受付に呼ばれていない人が存在する.
- ${\tt 2~x}$ : 人 $x$ は $1$ 回以上は受付に呼ばれていて, このイベントの直前までは人 $x$ は受付に行っていない.
- ${\tt 3}$ : 受付に呼ばれているが, 受付に行ってない人はいない.
- ${\tt 3}$ : この種類のイベントは $1$ 回以上起こる.

解法

${\tt 1}$ で呼ばれる人は順番に $1,2, \dots, N$ である.

よって, 次に ${\tt 1}$ で呼ばれる人を表わす変数 $\textrm{call}$ と受付に呼ばれたが受付に行っていない人の集合 $E$ を利用して, 次のようにして処理する.

$\textrm{call} \gets 1, E \gets \emptyset$ .
イベントの順に以下を行う.
- ${\tt 1}$ : $E$ に $\textrm{call}$ を加え, $\textrm{call}$ に $1$ を加算する.
- ${\tt 2~x}$ : $E$ から $x$ を削除する.
- ${\tt 3}$ : $E$ の最小値を取得する.

$E$ として順序つき集合を利用することにより, 計算量 $O(Q \log N)$ 時間で全て処理できる.