题解：P14507 缺零分治 mexdnc

先求出最大能够凑出的数，也就是

a_i

序列的

\rm mex

，记为

x

。

如果询问的数等于

x

，那么答案为

1

。

如果询问的数小于

x

，那么答案为

2

。（所有小于

x

的数分为一个集合，其他的一个集合）

如果询问的数大于

x

，那么肯定贪心地去凑每次最大能凑出的数，这样能使集合数量最少。

考虑预处理出每种值最多能凑出多少个。

从

x

到

1

枚举凑出的数

y

，查寻

1\sim y

中个数的最小值，最小值即为能凑出

y

的个数，然后给

1\sim y

的个数都减掉最小值。这里可以线段树维护。

查寻时一个二分即可。

注意特判

x

为

0

的情况。

CPP

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 10, inf = 1e18;

int n, q, X;
int a[N], b[N], cnt[N], m[N];

__int128 sum[N];
int sumc[N];

struct sgt {
    #define ls k << 1
    #define rs k << 1 | 1
    #define mid ((l + r) >> 1)
    int mi[N * 4], tag[N * 4];

    void pst( int k, int v) {
        mi[k] += v, tag[k] += v;
    }

    void psd( int k) {
        if (! tag[k]) return ;
        pst(ls, tag[k]), pst(rs, tag[k]);
        tag[k] = 0;
    }

    void build( int k = 1, int l = 1, int r = X) {
        mi[k] = inf, tag[k] = 0;
        if (l == r) return mi[k] = b[l], void();

        build(ls, l, mid), build(rs, mid + 1, r);
        mi[k] = min(mi[ls], mi[rs]);
    }

    void upd( int x, int y, int v, int k = 1, int l = 1, int r = X) {
        if (x <= l && r <= y) return pst(k, v);
        psd(k);

        if (x <= mid) upd(x, y, v, ls, l, mid);
        if (y > mid) upd(x, y, v, rs, mid + 1, r);
        mi[k] = min(mi[ls], mi[rs]);
    }

    int ask( int x, int y, int k = 1, int l = 1, int r = X) {
        if (x <= l && r <= y) return mi[k];
        psd(k);

        int res = inf;

        if (x <= mid) res = min(res, ask(x, y, ls, l, mid));
        if (y > mid) res = min(res, ask(x, y, rs, mid + 1, r));
        return res;
    }

    #undef mid
} T;

void solve() {
    cin >> n >> q;
    X = 0;

    for ( int i = 1; i <= n; i ++) {
        cin >> a[i] >> b[i];
        if (a[i] == X) X ++;
    }

    for ( int i = 1; i <= q; i ++) cin >> m[i];

    if (X == 0) {
        for ( int i = 1; i <= q; i ++) {
            int m = :: m[i];

            if (m == 0) cout << "1\n";
            else cout << "-1\n";
        }

        return ;
    }

    T.build();
    for ( int i = X; i; i --) {
        int mi = T.ask(1, i);
        cnt[i] = mi;
        T.upd(1, i, -mi);
    }

    sum[X + 1] = 0, sumc[X + 1] = 0;
    for ( int i = X; i; i --)
        sum[i] = sum[i + 1] + cnt[i] * i,
        sumc[i] = sumc[i + 1] + cnt[i];

    for ( int i = 1; i <= q; i ++) {
        int m = :: m[i];

        if (m == 0) {
            cout << "-1\n";
            continue ;
        }

        if (m == X) cout << "1\n";
        else if (m < X) cout << "2\n";
        else {
            if (m > sum[1]) {
                cout << "-1\n";
                continue ;
            }
            if (m <= sum[X]) {
                cout << (m / X) + ((m % X) != 0) << '\n';
                continue ;
            }

            int l = 1, r = X;

            while (l < r) {
                int mid = (l + r) >> 1;

                if (m > sum[mid]) r = mid;
                else l = mid + 1;
            }

            m -= sum[l];
            cout << sumc[l] + (m / (l - 1)) + ((m % (l - 1)) != 0) << '\n';
        }
    }
}

signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T; cin >> T;
    while (T --) solve();

    return 0;
}

题解：P14507 缺零分治 mexdnc

文章操作

相关推荐

评论

题解：P14507 缺零分治 mexdnc