Editorial for Khoảng trống giữa tinh tú

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 — đổi thứ tự xử lý truy vấn

Các truy vấn đều hỏi trên cùng một mảng tĩnh. Thay vì xử lý từng đoạn từ đầu, hãy sắp xếp truy vấn sao cho hai đầu mút thay đổi ít khi chuyển từ truy vấn này sang truy vấn khác.

Gợi ý 2 — giữ tần suất và chia miền giá trị thành khối

Dùng Mo để duy trì đoạn hiện tại. Mảng cnt[x] lưu số lần giá trị x xuất hiện trong đoạn. Chia các giá trị 0..N thành các khối; used[b] đếm có bao nhiêu giá trị khác nhau đang xuất hiện trong khối b.

Nếu một khối có đủ mọi giá trị trong miền của nó, MEX không nằm trong khối đó. Bỏ qua các khối đầy, rồi quét các giá trị của khối đầu tiên còn thiếu.

Lời giải đầy đủ

Cách duy trì đoạn

Khi thêm một phần tử có giá trị x, chỉ tăng used[x / B] nếu cnt[x] trước đó bằng 0. Khi xóa, chỉ giảm used[x / B] nếu cnt[x] trở về 0. Như vậy used đếm số giá trị phân biệt có mặt, không phải tổng tần suất.

Để lấy MEX, xét lần lượt các khối bắt đầu từ 0. Nếu số giá trị phân biệt trong khối bằng đúng độ rộng của khối, tất cả giá trị ở đó đều có mặt. Khối cuối có thể ngắn hơn B nên cần so sánh với độ rộng thực tế. Trong khối đầu tiên chưa đầy, tìm giá trị có cnt bằng 0.

MEX của một đoạn không vượt quá N vì độ dài đoạn nhiều nhất N; do đó chỉ cần xét miền 0..N.

Độ phức tạp

Với kích thước khối B xấp xỉ căn bậc hai của N, Mo di chuyển hai đầu mút khoảng O(N^2/B + QB) lần theo chặn trên. Mỗi lần lấy MEX quét tối đa O(N/B + B) giá trị/khối; bộ nhớ O(N+Q).

Code C++17
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500000 + 5;
const int MAXQ = 200000 + 5;
const int B = 707;

int a[MAXN], cnt[MAXN], presentInBlock[MAXN / B + 10];
int answer[MAXQ];

struct Query {
    int l, r, id;
};

void addPosition(int i) {
    int x = a[i];
    if (cnt[x]++ == 0) ++presentInBlock[x / B];
}

void removePosition(int i) {
    int x = a[i];
    if (--cnt[x] == 0) --presentInBlock[x / B];
}

int getMex(int n) {
    int block = 0;
    while (block * B <= n) {
        int left = block * B;
        int right = min(n, (block + 1) * B - 1);
        if (presentInBlock[block] != right - left + 1) break;
        ++block;
    }

    int x = block * B;
    while (x <= n && cnt[x] > 0) ++x;
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<Query> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }

    sort(queries.begin(), queries.end(), [](const Query& x, const Query& y) {
        int bx = x.l / B, by = y.l / B;
        if (bx != by) return bx < by;
        if (bx & 1) return x.r > y.r;
        return x.r < y.r;
    });

    int left = 1, right = 0;
    for (const Query& qu : queries) {
        while (left > qu.l) addPosition(--left);
        while (right < qu.r) addPosition(++right);
        while (left < qu.l) removePosition(left++);
        while (right > qu.r) removePosition(right--);
        answer[qu.id] = getMex(n);
    }

    for (int i = 0; i < q; ++i) cout << answer[i] << '\n';
    return 0;
}

Loading...