主题

主题

 
   

3339: Rmq Problem

原题:http://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


发现原来有一道双倍经验:

http://liaoy148.lofter.com/post/1da8a74e_ee06758

 
 
评论
 
 
热度(1)