题解：P14507 缺零分治 mexdnc

lichenxi111 · 2025-11-15 14:20:09 · 题解

思路

先考虑朴素做法，那么先处理出每个 mex 最多有多少个，显然我们只关注一个从 1 至 x 的一段连续的数，从大到小考虑，每个数能取就取，一定最优，细节不是很多。复杂度 O(Tqn)。

考虑优化，我们可以预处理出 s_i 表示把大于等于 i 的数能选的全选上的和，那么每次只需要二分查找第一个大于等于 m 的 s_i，这时把若干 i 变成更小的数即可使和为 m。

复杂度 O(Tq\log n)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
    int num = 0,f = 1;
    char c = getchar();
    while(!isdigit(c))
    {
        if(c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while(isdigit(c))
    {
        num = num * 10 + (c - '0');
        c = getchar();
    }
    return num * f;
}
struct node
{
    int a,b;
} a[110000];
int cnt[110000],sum[110000];
signed main()
{
    int T = read();
    while(T--)
    {
        int n = read(),q = read();
        for(int i = 1;i <= n;i++)
        {
            a[i].a = read();
            a[i].b = read();
        }
        cnt[0] = 2e9;
        int maxn = 0;
        for(int i = 1;i <= n;i++)
        {
            if(a[i].a == i - 1)
            {
                cnt[i] = min(cnt[i - 1],a[i].b);
            }
            else
            {
                cnt[i] = 0;
            }
            if(cnt[i])
            {
                maxn = max(maxn,i);
            }
        }
        cnt[maxn + 1] = 0;
        for(int i = maxn;i >= 1;i--)
        {
            sum[maxn - i + 1] = sum[maxn - i] + (cnt[i] - cnt[i + 1]) * i;
        }
        //cout << maxn << endl;
        while(q--)
        {
            int m = read();
            if(m == 0)
            {
                if(a[1].a == 0)
                {
                    cout << -1 << '\n';
                }
                else
                {
                    cout << 1 << '\n';
                }
                continue;
            }
            int t = lower_bound(sum + 1,sum + maxn + 1,m) - sum - 1;
            if(t == maxn)
            {
                cout << -1 << '\n';
                continue;
            }
            m -= sum[t];
            int k = maxn - t;
            int cntt = (m - 1) / k;
            //cout << cntt << endl;
            if(m < k && t == 0)
            {
                cout << 2 << '\n';
            }
            else
            {
                cout << cnt[k + 1] + cntt + 1 << '\n';
            }
        }
    }
    return 0;
}