BZOJ3339&3585 mex 莫队+树状数组

发布于 2017-09-24  4.28k 次阅读


[toggle hide="yes" title="题目" color=""]

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

[/toggle]

一开始想用动态开点线段树来维护最小未出现自然数,然而瞄了一眼题解告诉我会T掉,因为莫队算法(基本上)只适用于转移的复杂度为O(1)的操作,也就是说强行加个log2n比较难卡过去,所以考虑换用更高效的转移。

首先,即使是在极限情况下,我们最多只需要记录O(n)的出现信息,而不用考虑更大的数,因为最小未出现自然数一定就在这个范围内。有了这个性质,就可以用分块搞,转移时如果当前数在范围内,就暴力更新出现信息,同时在对应的块内记录。转移完成后,只要用O(sqrt(n))的时间复杂度跳块即可找到mex,总时间复杂度O((n+q)*sqrt(n))

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974