mex 题解

jzwjx · 2025-01-08 15:38:09 · 题解

题意简述

给定 n 个数，m 次询问，求区间最小未出现的自然数。

前置知识

莫队

一种分块后离线处理询问的算法，此处就不多说了，还不会的请自己查询。

bitset

一种很神奇的数据结构，可参考扶苏的 bitset 浅谈 - 洛谷专栏。

分析

由于没有修改，所以我们可以想到用莫队，维护区间内数的个数，那么只需要考虑如何快速查找从小到大的第一个没有出现的数字就好。

此时我们发现 bitset 有一个非常神器的函数——_Find_first(),它可以直接返回 bitset 里第一个 1 的下标，所以我们设 bitset 中 1 表示这个数字没有出现过，0 表示没有出现过，每回修改时维护当前数字 a_i 的出现次数 cnt_{a_i}，如果从 0 加为 1 就在 bitset 里把这一位赋为 0，如果从 1 减为 0 就在 bitset 里把这一位赋为 1，最后直接查询就做完了。

但如果仅是上述做法不开 O2 是会 TLE 一个点，所以我们此处引入莫队的一种优化——奇偶性排序。

我们可以发现，每次变到下一个块时，r 最劣会从最右边跑回当前块，所以我们可以在排序时根据所在块的奇偶性排序，若 i \equiv 1 \pmod {2}，则让 r 从大到小排序，否则从小到大排序。这样就可以在不开 O2 的情况下 A 掉此题了。

复杂度是 O(n\sqrt{n}+\dfrac{nq}{w})，理论上是超了的，但由于每次查询到的值和区间移动范围无法同时达到最大值，所以复杂度变为 O(能过)。

代码

莫队

for(int i=1;i<=q;i++){//莫队
        while(st[i].l<L){
            L--;
            add(a[L],1);
        }
        while(st[i].l>L){
            add(a[L],-1);
            L++;
        }
        while(st[i].r<R){
            add(a[R],-1);
            R--;
        }
        while(st[i].r>R){
            R++;
            add(a[R],1);
        }
        anss[st[i].id]=bit._Find_first();
    }

添加或删点

void add(int l,int x){
    if(x==1){
        if(cnt[l]==0) bit.set(l,0);//以前l没出现过
        cnt[l]++;
    }
    else {
        cnt[l]--;
        if(cnt[l]==0) bit.set(l,1);//当前区间内没有l了
    }
}

AC代码

这里。