Hướng giải của [Mo's] Đếm Khác

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán yêu cầu đếm số lượng phần tử khác nhau trên một đoạn liên tiếp. Đây là bài toán kinh điển có thể giải bằng Mo's Algorithm.

Ý tưởng:

  • Duy trì một mảng tần suất freq[val] và một biến distinct đếm số giá trị có tần suất dương.
  • Khi thêm một phần tử: nếu tần suất của nó tăng từ 0 lên 1, tăng distinct.
  • Khi xóa một phần tử: nếu tần suất của nó giảm từ 1 xuống 0, giảm distinct.
  • Sắp xếp các truy vấn theo thứ tự Mo's: theo khối của \(L\), và \(R\) tăng dần/giảm dần.

Độ phức tạp: \(O((N+Q)\sqrt{N})\).

Mã nguồn C++

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

int blockSize;
struct Query {
    int l, r, idx;
    bool operator<(const Query& o) const {
        int bl = l / blockSize, br = o.l / blockSize;
        if (bl != br) return bl < br;
        return (bl & 1) ? (r > o.r) : (r < o.r); // odd-even optimization
    }
};

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

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // Nén giá trị
    vector<int> comp(a.begin(), a.end());
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for (int i = 0; i < n; i++)
        a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();

    blockSize = max(1, (int)sqrt(n));
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].l--; queries[i].r--; // chuyển sang 0-indexed
        queries[i].idx = i;
    }
    sort(queries.begin(), queries.end());

    vector<int> ans(q);
    vector<int> freq(comp.size(), 0);
    int distinct = 0, curL = 0, curR = -1;

    auto add = [&](int pos) {
        if (freq[a[pos]] == 0) distinct++;
        freq[a[pos]]++;
    };
    auto remove = [&](int pos) {
        freq[a[pos]]--;
        if (freq[a[pos]] == 0) distinct--;
    };

    for (auto& qr : queries) {
        while (curL > qr.l) add(--curL);
        while (curR < qr.r) add(++curR);
        while (curL < qr.l) remove(curL++);
        while (curR > qr.r) remove(curR--);
        ans[qr.idx] = distinct;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << "\n";

    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.