/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ 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
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
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.