D - Range Count Query

Contest Duration: 2022-04-16(Sat) 12:00 - 2022-04-16(Sat) 13:40 (local time) (100 minutes) Back to Home

D - Range Count Query Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

長さ $N$ の数列 $A=(A_1,\ldots,A_N)$ が与えられます。

以下の形式で与えられる $Q$ 個のクエリに答えてください。

入力は以下の形式で標準入力から与えられる。

 $N$  
 $A_1$   $A_2$   $\ldots$   $A_N$ 
 $Q$ 
 $\mathrm{Query}_1$ 
 $\mathrm{Query}_2$ 
 $\vdots$ 
 $\mathrm{Query}_Q$

ただし、 $\mathrm{Query}_i$ は $i$ 個目のクエリを表す。

各クエリは以下の形式で与えられる。

 $L$   $R$   $X$

$Q$ 行出力せよ。 $i$ 行目には、 $i$ 個目のクエリに対する答えを出力せよ。

Copy

Copy

$1$ 個目のクエリでは、 $(A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5)$ のうち値が $1$ に等しいものの個数は $2$ です。

$2$ 個目のクエリでは、 $(A_2,A_3,A_4) =(1,4,1)$ のうち値が $3$ に等しいものの個数は $0$ です。

Score : $400$ points

You are given a sequence of length $N$ : $A=(A_1,\ldots,A_N)$ .

Answer $Q$ queries given in the following format.

You are given integers $L$ , $R$ , and $X$ . Find the number of elements among $A_L, \ldots, A_R$ whose values are equal to $X$ .

Input is given from Standard Input in the following format:

 $N$  
 $A_1$   $A_2$   $\ldots$   $A_N$ 
 $Q$ 
 $\mathrm{Query}_1$ 
 $\mathrm{Query}_2$ 
 $\vdots$ 
 $\mathrm{Query}_Q$

Here, $\mathrm{Query}_i$ represents the $i$ -th query.

Each query is in the following format:

 $L$   $R$   $X$

Print $Q$ lines, the $i$ -th of which contains the answer to the $i$ -th query.

Copy

Copy

In the first query, two of $(A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5)$ have values equal to $1$ .

In the second query, zero of $(A_2,A_3,A_4) =(1,4,1)$ have values equal to $3$ .