SP3267 DQUERY - D-query
题目描述
给定一个长度为 n 的整数数列 {a1,a2,…,an},以及 q 次询问。
每次询问给出一对整数 (i,j),其中 1≦i≦j≦n。对于这次询问,你需要回答子数组 {ai,ai+1,…,aj} 中不同元素的个数。例如子数组为 {1,2,1} 时,不同元素为 1 和 2,个数为 2。
输入格式
第一行输入一个整数 n(1≦n≦3×104) 代表数列长度。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^6\right)$ 代表数列中的元素。
第三行输入一个整数 q(1≦q≦2×105) 代表询问次数。
此后 q 行,第 t 行输入两个整数 $i_t, j_t \left(1 \leqq i_t \leqq j_t \leqq n\right)$ 代表第 t 次询问的区间。
输出格式
输出 q 行,第 t 行输出一个整数,代表第 t 次询问的子数组中不同元素的个数。
测试样例
5
1 1 2 1 3
3
1 5
2 4
3 5
3
2
3
样例 1 解释
数列为 {1,1,2,1,3},共有 3 次询问。
∙第 1 次询问的区间为 [1,5],对应子数组 {1,1,2,1,3},不同元素为 1,2,3,个数为 3;
∙第 2 次询问的区间为 [2,4],对应子数组 {1,2,1},不同元素为 1,2,个数为 2;
∙第 3 次询问的区间为 [3,5],对应子数组 {2,1,3},不同元素为 1,2,3,个数为 3。
6
1 2 2 3 1 4
4
1 6
2 3
1 4
5 6
4
1
3
2
样例 2 解释
数列为 {1,2,2,3,1,4},共有 4 次询问。
∙第 1 次询问的区间为 [1,6],对应子数组 {1,2,2,3,1,4},不同元素为 1,2,3,4,个数为 4;
∙第 2 次询问的区间为 [2,3],对应子数组 {2,2},不同元素只有 2,个数为 1;
∙第 3 次询问的区间为 [1,4],对应子数组 {1,2,2,3},不同元素为 1,2,3,个数为 3;
∙第 4 次询问的区间为 [5,6],对应子数组 {1,4},不同元素为 1,4,个数为 2。