LG#P1972. [SDOI2009] HH 的项链

[SDOI2009] HH 的项链

P1972 [SDOI2009] HH 的项链

题目描述

\hspace{15pt}HH 有一串由各种漂亮贝壳组成的项链。HH 相信不同种类的贝壳会带来好运,所以每次散步结束后,他都会随意取出一段贝壳,思考它们表达的含义。

\hspace{15pt}HH 不断地收集新的贝壳,项链变得越来越长。有一天,他突然想到一个问题:某一段贝壳中,包含了多少种不同的贝壳?因为项链实在太长,他只好求助睿智的你。

\hspace{15pt}给定一条长度为 nn 的项链,第 ii 个贝壳的种类为 aia_i。另有 mm 次询问,第 ii 次询问给出区间 [li,ri][l_i, r_i],请回答该区间内不同贝壳种类的数量。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦106)n \left(1 \leqq n \leqq 10^6\right) 代表项链长度。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^6\right)$ 代表项链中每个贝壳的种类。

\hspace{15pt}第三行输入一个整数 m(1≦m≦106)m \left(1 \leqq m \leqq 10^6\right) 代表询问数量。

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

输出格式

\hspace{15pt}输出 mm 行,第 ii 行输出一个整数,代表第 ii 次询问的区间内不同贝壳种类的数量。

测试样例

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

样例 1 解释

\hspace{15pt}项链上贝壳的种类依次为 {1,2,3,4,3,5}\{1, 2, 3, 4, 3, 5\}:

∙ \hspace{23pt}\bullet\,第 11 次询问区间 [1,2][1,2],贝壳种类为 {1,2}\{1,2\},共 22 种;

∙ \hspace{23pt}\bullet\,第 22 次询问区间 [3,5][3,5],贝壳种类为 {3,4,3}\{3,4,3\},去重后为 {3,4}\{3,4\},共 22 种;

∙ \hspace{23pt}\bullet\,第 33 次询问区间 [2,6][2,6],贝壳种类为 {2,3,4,3,5}\{2,3,4,3,5\},去重后为 {2,3,4,5}\{2,3,4,5\},共 44 种。

\hspace{15pt}因此依次输出 2,2,42,2,4。

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

提示

\hspace{15pt}对于 20%20\% 的数据,1≦n,m≦5×1031 \leqq n, m \leqq 5 \times 10^3;

\hspace{15pt}对于 40%40\% 的数据,1≦n,m≦1051 \leqq n, m \leqq 10^5;

\hspace{15pt}对于 60%60\% 的数据,1≦n,m≦5×1051 \leqq n, m \leqq 5 \times 10^5;

\hspace{15pt}对于 100%100\% 的数据,1≦n,m,ai≦1061 \leqq n, m, a_i \leqq 10^6,1≦li≦ri≦n1 \leqq l_i \leqq r_i \leqq n。