Kazun の競プロ記録

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

AtCoder Beginner Contest 235 C 問題 The Kth Time Query

AtCoder ABC ABC235 C問題 300 pts

問題

提出解答

問題の概要

長さ $N$ の列 $A=(a_1, \dots, a_N)$ が与えられる.

次の $Q$ 個の質問に答えよ. ただし, $q$ 番目の質問は整数の組 $(x_q, k_q)$ で与えられる.

$A$ の項を第 $1$ 項から見たとき, $x_q$ が $k_q$ 回目に登場するのは $A$ の第何項目か (存在しない場合, その旨を報告せよ)?

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq a_i \leq 10^9$
$1 \leq x_q \leq 10^9$
$1 \leq k_q \leq N$

解法

以下のようなデータ構造 $(X,D)$ を作成する.

$X(y)$ は $A$ に $y$ が何回登場するかを記録する.
$D(y)$ は長さ $X(y)$ の配列で, $D(y)$ の第 $i$ 項目には, $A$ において, $y$ が $i$ 番目に登場するときの $A$ の添字番号とする.

このようなデータ構造は辞書やリストを用いて作成できる (なお, $X(y)$ は $D(y)$ から求められる場合もあるので, 場合によっては省略可能).

このデータ構造 $(X,D)$ を用いて, 質問 $(x_q, k_q)$ に答えることができる.

$k_q \gt X(x_q)$ ならば, 答えは存在しない.
$k_q \leq X(x_q)$ ならば, $D(x_q)$ の第 $k_q$ 項目が答えである.

以上から計算量 $O((N+Q) \log N)$ や $O(N+Q)$ で求めることができる.