[Luogu]P4137 Rmq Problem/Mex
本文最后更新于 197 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/lp4137/

题意

题目传送门

有一个长度为 $n$ 的数组 $\{a_1,a_2,\ldots,a_n\}$。$m$ 次询问,每次询问一个区间内最小没有出现过的自然数。

解法

可以使用回滚莫队求解。

记数字 $i$ 出现次数为 $cnt_i$,使得 $cnt_i = 0$ 成立的最小 $i$ 值。

不难发现,$\text{ans} \leq n$,即 $0,1,\ldots,n – 1$ 时的情况,因此大于等于 $n$ 的数无需处理。

数次数问题,常用莫队来求解,考虑添加、删除的影响:

  1. 删除时,$cnt_x$ 自减,若为 $0$ 则与 $\text{ans}$ 比较取最小值更新。
  2. 增加时,$cnt_x$ 自增,若 $x = ans$ 则需要找到新的答案。

删除的操作复杂度为 $O(1)$ 的,但增加后找答案较为困难。

有的题解使用了循环找,复杂度是错误的,会被第11组数据卡掉。亲身试验

笔者曾经尝试使用线段树来维护,总复杂度 $O(n\sqrt{n}\log n)$ 能通过第11组数据,前面的测试点却会TLE。

此时可以使用回滚莫队。

当莫队的增加、删除操作中,某操作是不可行或复杂度过高的,可以考虑不使用该操作。

在本题中,可以不使用增加操作,只使用删除操作,那么就是一道只使用删除的回滚莫队的题目。

关于回滚莫队可以看OI-Wiki上的讲解

块内暴力的做法不再赘述了,这里讲讲跨块如何操作。

只使用删除操作,要求左指针单调递增,右指针单调递减。

因此跨块时,将左指针设为该块的左端点,右指针设为 $n$。

还需要更新初状态,直接扫描区间,从小到大遍历 $\text{ans}$ 值更新即可,复杂度 $O(n)$。

由于块数最多 $\sqrt{n}$ 块,那么复杂度仍为 $O(n\sqrt{n})$。

还有一点,由于右指针单调递减,排序要按 $r$ 降序排序。

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctype.h>
#define DEBUG
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T &r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c);) c = nc();
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 2e5 + 100;
int n, m, L[maxn], R[maxn], pos[maxn];
int a[maxn], cnt[maxn], tempcnt[maxn], ANS[maxn];
struct node
{
    int l, r, id;
} Q[maxn];
bool cmp(const node &a, const node &b)
{
    if (pos[a.l] != pos[b.l]) return a.l < b.l;
    return a.r > b.r;
}
inline void build()
{
    int size = n / std::sqrt(m);
    int num = n / size;
    for (int i = 1; i <= num; ++i)
    {
        L[i] = R[i - 1] + 1, R[i] = L[i] + size - 1;
        for (int j = L[i]; j <= R[i]; ++j) pos[j] = i;
    }
    if (R[num] < n)
    {
        L[num + 1] = R[num] + 1, R[++num] = n;
        for (int i = L[num]; i <= n; ++i) pos[i] = num;
    }
}
inline void del(int x, int &ans)
{
    if (x >= n) return;
    if (--cnt[x] == 0) ans = std::min(ans, x);
}
inline void init()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= m; ++i) read(Q[i].l), read(Q[i].r), Q[i].id = i;
    build();
    std::sort(Q + 1, Q + 1 + m, cmp);
}
int main()
{
    init();
    int l = 1, r = 0, ans = 0, lastblock = 0;
    for (int i = 1; i <= m; ++i)
    {
        if (pos[Q[i].l] == pos[Q[i].r])
        {
            for (int j = Q[i].l; j <= Q[i].r; ++j) if (a[j] < n) tempcnt[a[j]]++;
            for (; tempcnt[ANS[Q[i].id]] > 0; ++ANS[Q[i].id]);
            for (int j = Q[i].l; j <= Q[i].r; ++j) tempcnt[a[j]] = 0;
            continue;
        }
        if (pos[Q[i].l] != lastblock)
        {
            int p = pos[Q[i].l];
            l = L[p], r = n, lastblock = p;
            for (int j = 0; j <= n; ++j) cnt[j] = 0;
            for (int j = l; j <= r; ++j) if (a[j] < n) cnt[a[j]]++;
            for (ans = 0; cnt[ans] > 0; ++ans);
        }
        while (r > Q[i].r) del(a[r--], ans);
        ANS[Q[i].id] = ans;
        for (int j = l; j < Q[i].l; ++j) del(a[j], ANS[Q[i].id]);
        for (int j = l; j < Q[i].l; ++j) cnt[a[j]]++;
    }
    for (int i = 1; i <= m; ++i) printf("%d\n", ANS[i]);
    return 0;
}
本文标题:[Luogu]P4137 Rmq Problem/Mex
本文作者:Clouder
本文链接: https://www.codein.icu/lp4137/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇