ABC463 C - Tallest at the Moment

各瞬間のノッポ

考え方

時系列にそって何かが起こる話なので、イベントソートで考えたいところ。
しかし、高橋くんが入室なら扱いやすいが、退出すなわちデータの削除は大変。
そこで、時間軸を反転し、逆再生で解いていくことを考える。

まず、クエリを全て先読みし、時刻が遅い順に並べておく。
また、高橋くんも、退出時刻が遅い順に並べておく。

そして、クエリを遅い順に見ていく。
あるクエリを見たときには、その時刻より後に退出した高橋くんをすべて部屋の中に戻せばよい。

これなら高橋くんの（データ的な意味で）退出が発生しないので、最高身長を変数 $1$ つで持てば十分。
クエリを処理するごとに本来のクエリ番号のところに結果を書き込んでいけばよい。
計算量は、ソートがボトルネックで $O(N \log N + Q \log Q)$。

入力を受け取る。

n: 4
h: {31, 26, 3, 15}
l: {4, 5, 5, 9}
q: 4
t: {3, 4, 5, 6}

クエリを時刻の遅い順に見ると、$6,5,4,3$ の順になる。
逆再生では、各時刻より後に退出する高橋くんを部屋へ戻す。
戻すたびに、現在の最高身長を更新する。

クエリ時刻 $T$	新たに部屋へ戻す身長	その時点での最高身長	元のクエリへの答え
$6$	$\{15\}$	$15$	$4$ 番目：$15$
$5$	なし	$15$	$3$ 番目：$15$
$4$	$\{26,3\}$	$26$	$2$ 番目：$26$
$3$	$\{31\}$	$31$	$1$ 番目：$31$

元のクエリ順に並べると、答えは $31,26,15,15$ となる。

特になし。

特になし。