3377: 不同的数字(hard)
内存限制：256 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：96
解决：9
题目描述
对于一个长度为n的数组a_1,a_2,...,a_n
你将会得到m次询问,每次询问给出l,r,你需要计算出a_l,a_(l+1),...,a_r中有多少个不同的数字
如1,2,2,3,3中有3个不同的数字,分别是1,2,3
你将会得到m次询问,每次询问给出l,r,你需要计算出a_l,a_(l+1),...,a_r中有多少个不同的数字
如1,2,2,3,3中有3个不同的数字,分别是1,2,3
输入
输入第一行两个整数n(1<=n<=1e5)，代表数组长度,m(1<=m<=1e5),代表询问个数
第二行有n个数字,代表给定的数组.(1<=a_i<=1e6)
接下来m行,每行给出一个l,r,代表询问.(1<=l<=r<=n)
第二行有n个数字,代表给定的数组.(1<=a_i<=1e6)
接下来m行,每行给出一个l,r,代表询问.(1<=l<=r<=n)
输出
对于每个询问输出一行,每行一个整数,代表区间内不同数字的个数.
样例输入 复制
5 3
1 1 2 1 3
1 5
2 4
3 5样例输出 复制
3
2
3