题解：P14132 【MX-X22-T3】「TPOI-4C」Another MEX Problem

· · 题解

前置

本做法写起来简单，用的知识也是普及组范围内的，请放心阅读。

思路

首先我们理解题意，这里的 \operatorname{mex}=x 指的是以 [x,x+k-1] 区间内的数字都没有出现。

对于一些已经出现的数字，我们要添加最多 m 个数字使得 \operatorname{mex} 最大，也就是考虑每一段值域的空隙（排序后相邻两数中间），我们每隔 k 放一个数字，来尽可能优地填满。

假设两个相邻的已有数字是 l,r，那么空隙中需要填的数字数量就是 \lfloor\frac{r-l-1}{k}\rfloor（\lfloor x\rfloor 为向下取整）。

所以我们考虑逐步加入数字的过程，可以维护一个链表表示所有区间，并维护每个区间需要多少数来填充。

加入一个数就相当于在链表某个位置插入这个数。为了找到这个位置，可以使用 set 找到第一个小于这个数的数，并用 unordered_map 找到这个数字在链表中的位置。

然后就可以更新前后两段空隙的“需要填多少个数”。

我们还需要实时维护一个位置 pos，表示当前的最大 \operatorname{mex} 大致链表的什么地方；除此之外再维护剩下多少个可用数字。这样如果加数后需要的数更少了，并且加数的位置在 pos 前面，那么可用数字就增加。如果当前的可用数字数量足以让 pos 跳到链表下一段，就去跳，并减少可用数字（此处具体可以参考代码）。

回顾一遍加数过程：

时间复杂度 O(Tn\operatorname{log}n)。

::::info[参考实现]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T, n, m, k, a[200010], b[200010];
int nxt[200010], val[200010], num[200010];
int tp = 0;
unordered_map<int, int> mp;
set<int> s;
void pres() {
    s.clear(), mp.clear();
    s.insert(-1), s.insert(1e18);
    nxt[1] = 2, val[1] = 1e18;
    num[1] = -1, num[2] = 1e18;
    mp[-1] = 1, mp[1e18] = 2;
    tp = 2;
}
signed main() {
    cin >> T;
    while (T--) {
        pres();
        cin >> n >> m >> k;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int ans = 0, pos = 1, cur = 0;
        for (int i = 1; i <= n; i++) {
            if(s.find(a[i]) == s.end()){
                auto it = s.lower_bound(a[i]);
                int l = mp[*--it], r = nxt[l], d = val[l];
                s.insert(a[i]);
                mp[a[i]] = ++tp, num[tp] = a[i];
                val[l] = (a[i] - num[l] - 1) / k, d -= val[l];
                val[tp] = (num[r] - a[i] - 1) / k, d -= val[tp];
                nxt[l] = tp, nxt[tp] = r;
                if (num[pos] >= num[r]) cur -= d;
                while (cur + val[pos] <= m)
                    cur += val[pos], pos = nxt[pos];
                ans = num[pos] + (m - cur) * k + 1;
            }
            cout << ans << " ";
        }
        cout << endl;
    }
    return 0;
}

::::