P1972 [SDOI2009] HH 的项链
题目描述
HH 有一串由各种漂亮贝壳组成的项链。HH 相信不同种类的贝壳会带来好运,所以每次散步结束后,他都会随意取出一段贝壳,思考它们表达的含义。
HH 不断地收集新的贝壳,项链变得越来越长。有一天,他突然想到一个问题:某一段贝壳中,包含了多少种不同的贝壳?因为项链实在太长,他只好求助睿智的你。
给定一条长度为 n 的项链,第 i 个贝壳的种类为 ai。另有 m 次询问,第 i 次询问给出区间 [li,ri],请回答该区间内不同贝壳种类的数量。
输入格式
第一行输入一个整数 n(1≦n≦106) 代表项链长度。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^6\right)$ 代表项链中每个贝壳的种类。
第三行输入一个整数 m(1≦m≦106) 代表询问数量。
此后 m 行,第 i 行输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq n\right)$ 代表第 i 次询问的区间。
输出格式
输出 m 行,第 i 行输出一个整数,代表第 i 次询问的区间内不同贝壳种类的数量。
测试样例
6
1 2 3 4 3 5
3
1 2
3 5
2 6
2
2
4
样例 1 解释
项链上贝壳的种类依次为 {1,2,3,4,3,5}:
∙第 1 次询问区间 [1,2],贝壳种类为 {1,2},共 2 种;
∙第 2 次询问区间 [3,5],贝壳种类为 {3,4,3},去重后为 {3,4},共 2 种;
∙第 3 次询问区间 [2,6],贝壳种类为 {2,3,4,3,5},去重后为 {2,3,4,5},共 4 种。
因此依次输出 2,2,4。
7
2 3 2 1 3 2 4
4
1 3
2 6
3 7
5 5
2
3
4
1
提示
对于 20% 的数据,1≦n,m≦5×103;
对于 40% 的数据,1≦n,m≦105;
对于 60% 的数据,1≦n,m≦5×105;
对于 100% 的数据,1≦n,m,ai≦106,1≦li≦ri≦n。