关于区间Mex问题的算法整理

给你一个长度为n的数列,元素编号1到n,第i个元素值为Ai。现在有m个形如(L,R)的提问,你需要回答出区间[L,R]的mex值。即求出区间[L,R]中没有出现过的最小的非负整数。

该问题被称为区间Mex问题,这个问题的解法多种多样,下面给出3种不同解法

由于没有修改操作,我们可以考虑离线。

对于一个固定的左端点,我们可以在的复杂度内求出每个右端点的答案。

首先对于那些值大于等于的肯定对答案没用。

然后开一个数组(桶)记录一下小于的每个值有没有出现,然后用一个指针不停的向上爬就好了。

由于指针只增不降,所以均摊复杂度

然后考虑对于一个左端点对于下一个左端点有什么影响。

只需要消除对于之后那些影响就好了,会对哪些有影响呢?

只会对下一个产生影响。

只需要有一个数据结构支持区间修改(将区间内大于等于的数修改为)即可。线段树