3339: Rmq Problem
原题:https://www.lydsy.com/JudgeOnline/problem.php?id=3339
Description
有一个长度为n的数组{a1,a2,…,an}。m次询问,每次询问一个区间内最小没有出现过的自然数。
Input
第一行n,m。
第二行为n个数。
从第三行开始,每行一个询问l,r。
Output
一行一个数,表示每个询问的答案。
Sample Input
5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
Sample Output
1
2
3
0
3
HINT
数据规模和约定
对于100%的数据:
1<=n,m<=200000
0<=ai<=109
1<=l<=r<=n
对于30%的数据:
1<=n,m<=1000
个人解法:
mex应该是可以合并的,记得谁说过?然而不太记得了。
然后想莫队。
维护桶。
然后修改就修改好了。查询mex可以扫一遍桶。
所以分块维护桶。
代码如下:
https://code.csdn.net/snippets/2218330
发现原来有一道双倍经验: