3378: 不同的数字(super hard)
内存限制：256 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：10
解决：4
题目描述
对于一个长度为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行,每行给出一个d,询问的l,r由d生成,规则如下
l=lastans,r=min(l+d,n);其中lastans是上一次询问的答案,最开始lastans=1;
第二行有n个数字,代表给定的数组.(1<=a_i<=1e6)
接下来m行,每行给出一个d,询问的l,r由d生成,规则如下
l=lastans,r=min(l+d,n);其中lastans是上一次询问的答案,最开始lastans=1;
输出
对于每个询问输出一行,每行一个整数,代表区间内不同数字的个数.
样例输入 复制
5 3
1 1 2 1 3
1
5
3样例输出 复制
1
3
3