Kazun の競プロ記録

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

AtCoder Beginner Contest 248 D問題 Range Count Query

AtCoder ABC ABC248 D問題 400 pts

問題

提出解答

問題の概要

整数列 $A=(A_i)_{i=1}^N$ が与えられる. 次の質問に $Q$ 個答えよ.

$A_L, \dots, A_R$ にある $X$ の個数を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq N$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq L \leq R \leq N$
$1 \leq X \leq N$

解法

$k=1,2, \dots, N$ に対して, $\chi_A(k)$ で $A$ にある $k$ の個数とする.

このとき, 列 $I_k=\left(i_{k,j} \right)_{j=1}^{\chi_A(k)}$ を以下を満たすような列とする (このような列達は $A$ から一意に定まる).

$1 \leq i_{k, 1} \lt i_{k,2} \lt \dots \lt i_{k, \chi_A(k)} \leq N$
$A_{i_{k,j}}=k \quad (1 \leq j \leq \chi_A(k))$

この $I_k$ は $A_i=k$ を満たす $i$ を昇順に並べた列である. $I_k$ を用いることになり, この問題は

$I_X$ にある $L$ 以上 $R$ 以下の整数の個数

に帰着される.

帰着された問題の解法を考える. $I_X$ にある $\alpha$ 以下の整数の個数を $\beta(I_X, \alpha)$ と書くことにすると, 帰着された問題の答えは $\beta(I_X,R)-\beta(I_X, L-1)$ である. そして, $I_X$ は昇順にならんでいることから, $\beta(I_X, \alpha)$ は二分探索で高速に求めることができる.

以上から, $Q$ 個の問題を $I_X$ を前計算で求め, 各問に対して二分探索を利用することにより, 時間計算量 $O(N+Q \log N)$ で処理できる.