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

szh_AK_all · 2025-10-05 10:18:29 · 题解

彻底怒了，这题我调了超级久。

暴力思路很简单，就是我们把当前所有数排个序，然后如果相邻两个数 x,y 满足 y-x>k，则我们需要用 \lfloor \frac{y-x-1}{k}\rfloor 次操作把他填满，当然在边界的时候不一定能填满，特判即可。

考虑怎么优化这个过程，首先把当前数排序以及计算相邻两数的差值可以用 set 优化，然后因为答案单调不减，我们在上一次可以填满的位置，在这一次一定也能填满，于是再开一个 set 记录我们需要填满的位置，然后从上一个填满的位置继续暴力计算还能填满到哪个位置。

常数超级大，代码超级难写。

::::info[Code]

#include <bits/stdc++.h>
using namespace std;
int a[1000005];

struct node {
    int x, y;
    inline friend bool operator<(node l, node r) {
        if (l.x != r.x)
            return l.x < r.x;
        return l.y < r.y;
    }
    inline node(int aa = 0, int bb = 0) {
        x = aa;
        y = bb;
    }
};
int wan, yong, dang, now;

signed main() {
    int t, n, m, k, z1, z2;
    scanf("%d", &t);
    set<int>s;
    set<node>ss;
    auto it = s.begin();
    auto itt = ss.begin();
    while (t--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        now = 0;
        s.clear(), ss.clear();
        s.insert(-1);

        wan = -2, yong = 0, dang = -1;
        for (int i = 1; i <= n; i++) {
            if (s.find(a[i]) == s.end()) {
                s.insert(a[i]);
                it = s.find(a[i]);
                z1 = *(--it);
                it++;
                it++;
                z2 = -100;
                if (it != s.end())
                    z2 = *(it);
                if (z2 >= 0)
                    ss.erase(node(z1, (z2 - z1 - 1) / k));
                if (z2 - z1 > k && z2 >= 0) {
                    now -= (z2 - z1 - 1) / k;
                    if (wan >= z1)
                        yong -= (z2 - z1 - 1) / k;
                }
                ss.insert(node(z1, (a[i] - z1 - 1) / k));
                if (a[i] - z1 > k) {
                    now += (a[i] - z1 - 1) / k;
                    if (wan >= z1)
                        yong += (a[i] - z1 - 1) / k;
                }
                if (z2 >= 0)
                    ss.insert(node(a[i], (z2 - a[i] - 1) / k));
                if (z2 - a[i] > k && z2 >= 0) {
                    now += (z2 - a[i] - 1) / k;
                    if (wan >= z1)
                        yong += (z2 - a[i] - 1) / k;
                }
                if (z2 - z1 > k && z2 >= 0 && wan >= z1)
                    wan = max(wan, a[i]);
            }
            if (m >= now) {
                it = s.end();
                it--;
                itt = ss.end();
                if (itt != ss.begin()) {
                    wan = (*(--itt)).x;
                    yong = now;
                    dang = (*it);
                }
                printf("%lld ", ((*it) + 1LL * (m - now) * k + 1));
            } else {
                int zz = yong, no = dang;
                itt = ss.lower_bound(node(dang, 0));
                while (itt != ss.end() && (*itt).x == wan)
                    itt++;
                while (1) {
                    if (itt == ss.end())
                        break;
                    node x = *itt;
                    int kk = min(x.y, m - zz);
                    no = x.x + min(x.y, m - zz) * k;
                    zz += min(x.y, m - zz);
                    if (zz == m && kk != x.y)
                        break;
                    itt++;
                    wan = x.x;
                    if (!x.y)
                        ss.erase(x);
                    yong = zz;
                    dang = no;
                }
                printf("%d ", no + 1);
            }
        }
        puts("");
    }
}
/*
1
8 4 1
3 12 7 8 11 0 10 1
*/

::::