#SP3267. D-询问

D-询问

SP3267 DQUERY - D-query

题目描述

\hspace{15pt}给定一个长度为 nn 的整数数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},以及 qq 次询问。

\hspace{15pt}每次询问给出一对整数 (i,j)(i, j),其中 1≦i≦j≦n1 \leqq i \leqq j \leqq n。对于这次询问,你需要回答子数组 {ai,ai+1,…,aj}\{a_i, a_{i+1}, \dots, a_j\} 中不同元素的个数。例如子数组为 {1,2,1}\{1, 2, 1\} 时,不同元素为 11 和 22,个数为 22。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦3×104)n \left(1 \leqq n \leqq 3 \times 10^4\right) 代表数列长度。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^6\right)$ 代表数列中的元素。

\hspace{15pt}第三行输入一个整数 q(1≦q≦2×105)q \left(1 \leqq q \leqq 2 \times 10^5\right) 代表询问次数。

\hspace{15pt}此后 qq 行,第 tt 行输入两个整数 $i_t, j_t \left(1 \leqq i_t \leqq j_t \leqq n\right)$ 代表第 tt 次询问的区间。

输出格式

\hspace{15pt}输出 qq 行,第 tt 行输出一个整数,代表第 tt 次询问的子数组中不同元素的个数。

测试样例

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

样例 1 解释

\hspace{15pt}数列为 {1,1,2,1,3}\{1, 1, 2, 1, 3\},共有 33 次询问。

∙ \hspace{23pt}\bullet\,第 11 次询问的区间为 [1,5][1, 5],对应子数组 {1,1,2,1,3}\{1, 1, 2, 1, 3\},不同元素为 1,2,31, 2, 3,个数为 33;

∙ \hspace{23pt}\bullet\,第 22 次询问的区间为 [2,4][2, 4],对应子数组 {1,2,1}\{1, 2, 1\},不同元素为 1,21, 2,个数为 22;

∙ \hspace{23pt}\bullet\,第 33 次询问的区间为 [3,5][3, 5],对应子数组 {2,1,3}\{2, 1, 3\},不同元素为 1,2,31, 2, 3,个数为 33。

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

样例 2 解释

\hspace{15pt}数列为 {1,2,2,3,1,4}\{1, 2, 2, 3, 1, 4\},共有 44 次询问。

∙ \hspace{23pt}\bullet\,第 11 次询问的区间为 [1,6][1, 6],对应子数组 {1,2,2,3,1,4}\{1, 2, 2, 3, 1, 4\},不同元素为 1,2,3,41, 2, 3, 4,个数为 44;

∙ \hspace{23pt}\bullet\,第 22 次询问的区间为 [2,3][2, 3],对应子数组 {2,2}\{2, 2\},不同元素只有 22,个数为 11;

∙ \hspace{23pt}\bullet\,第 33 次询问的区间为 [1,4][1, 4],对应子数组 {1,2,2,3}\{1, 2, 2, 3\},不同元素为 1,2,31, 2, 3,个数为 33;

∙ \hspace{23pt}\bullet\,第 44 次询问的区间为 [5,6][5, 6],对应子数组 {1,4}\{1, 4\},不同元素为 1,41, 4,个数为 22。