主题

主题

 
   

3585: mex

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3585

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<=10^9

  1<=l<=r<=n

  对于30%的数据:

  1<=n,m<=1000


个人解法:


  • 主席树

建一棵数字大小为下标的可持久化线段树。

每个节点的权值为出现的最右端的位置。那么对于一段区间[l,r]的查询,root[r]下的所有的叶子就可以代表[1,r]的出现。

我们要找的mex,就是找尽量左边的(数字尽量小),最右边的位置小于l的数字(由于我们记录的是出现的最右端的位置,如果这个数字权值小于l,这个数字就不在这个[l..r]出现过)。

所以在这里我们要假设没有出现过的数字的叶子节点权值为0。

线段树维护最小值即可。

每一次查询,先查询左边的最小值。如果左边的最小值小于l,说明mex在左边,否则在右边。


代码如下:

https://code.csdn.net/snippets/2294379


 

  • 莫队

我们使用莫队移动,维护一个桶。

拿到这个桶以后,就是要找最小出现的元素。

看了WerKeyTom_FTD大爷一篇博客,说mex可以暴力移动。且可以证明暴力移动的时间复杂度的上限是与暴力移动询问同阶的。

但是本蒟并不会证明,WerKeyTom_FTD大爷也没有详细说明。

然后自己想了一些方法。

首先拿一棵线段树自然是很好维护的。但是复杂度增加了logn了。已经承受不了了。

于是我们考虑分块维护这个桶。

每一次查询就是按顺序扫描过来,如果有一个块元素个数不等于块的长度,就说明这里有一个格子空了,就扫描这一个块,找到并返回答案。

注意分块里面维护的元素的个数不是数字的多少。


代码如下:

https://code.csdn.net/snippets/2294649

(刚开始发现把询问与分块的阈值弄混了,然后跑得很慢。后来调整了一下,结果发现更慢了……诡异)


 
 
评论