提出 #74114837

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

void update(vector<int> &fenwick, int index, int value) {
    while (index < (int)fenwick.size()) {
        fenwick[index] += value;
        index += index & -index;
    }
}
int query(const vector<int> &fenwick, int index) {
    int sum = 0;
    while (index) {
        sum += fenwick[index];
        index -= index & -index;
    }
    return sum;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(1+n);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int q; cin >> q;
    vector<pair<long long, int>> queries(q);
    for (int i = 0; i < q; ++i) {
        queries[i].second = i;
        cin >> queries[i].first;
    }
    sort(queries.begin(), queries.end());

    map<int, int> freq;
    for (int i = 1; i <= n; ++i) ++freq[a[i]];
    const int missingVals = m - freq.size();
    map<int, vector<int>> fs;
    for (auto [x, f] : freq) fs[f].push_back(x);
    vector<pair<int, vector<int>>> byFreq;
    for (auto &[x, v] : fs) byFreq.emplace_back(x, v);

    vector<int> qAns(q);
    int nextQ = 0;
    while (nextQ < q && queries[nextQ].first <= n) {
        qAns[queries[nextQ].second] = a[queries[nextQ].first];
        ++nextQ;
    }

    // after pos lastEnd every value has frequency >= lastFreq
    long long lastEnd = n, lastFreq = 0, vals = missingVals;
    vector<int> fenwick(1+m);
    for (int v = 1; v <= m; ++v) {
        if (!freq.count(v)) update(fenwick, v, +1);
    }
    auto kthSmallest = [&](int k) { // find kth smallest value in fenwick tree
        assert(1 <= k && k <= vals);
        int l = 0, r = m;
        while (l+1 < r) {
            int mid = (l+r) / 2;
            if (query(fenwick, mid) >= k) r = mid;
            else l = mid;
        }
        return r;
    };

    for (auto &[f, v] : byFreq) {
        int df = f-lastFreq;
        long long blockSize = df * vals;

        while (nextQ < q && queries[nextQ].first <= lastEnd + blockSize) {
            int valInBlock = (queries[nextQ].first - lastEnd - 1) % vals + 1;
            qAns[queries[nextQ].second] = kthSmallest(valInBlock);
            ++nextQ;
        }
        lastEnd += blockSize;
        lastFreq = f;
        vals += v.size();
        for (int x : v) update(fenwick, x, +1);
    }
    // infinite block at the end
    assert(vals == m);
    while (nextQ < q) {
        int valInBlock = (queries[nextQ].first - lastEnd - 1) % vals + 1;
        qAns[queries[nextQ].second] = kthSmallest(valInBlock);
        ++nextQ;
    }

    for (int x : qAns) cout << x << '\n';
    return 0;
}

提出情報

ジャッジ結果