102483: [AtCoder]ABC248 D - Range Count Query

Problem Statement

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$.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq N$
• $1 \leq Q \leq 2\times 10^5$
• $1\le L \leq R \leq N, 1 \leq X \leq N$, for each query.
• All values in input are integers.

Input

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$

Output

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

Sample Input 1

5
3 1 4 1 5
4
1 5 1
2 4 3
1 5 2
1 3 3

Sample Output 1

2
0
0
1

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$.

问题描述

你被给定一个长度为$N$的序列：$A=(A_1,\ldots,A_N)$。

回答以下格式给出的$Q$个查询。

• 你被给定整数$L$，$R$和$X$。 找出$A_L, \ldots, 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\le L \leq R \leq N, 1 \leq X \leq N$，对于每个查询。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$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$个查询的答案。

样例输入1

5
3 1 4 1 5
4
1 5 1
2 4 3
1 5 2
1 3 3

样例输出1

2
0
0
1

在第一个查询中，$(A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5)$中有两个元素的值等于$1$。

在第二个查询中，$(A_2,A_3,A_4) =(1,4,1)$中没有元素的值等于$3$。