Hướng giải của [Mo's] Tần Suất

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ần xuất hiện của một giá trị \(X\) trong một đoạn. Sử dụng Mo's Algorithm với mảng tần suất.

Ý tưởng:

  • Duy trì mảng freq[val] — tần suất hiện tại của từng giá trị.
  • Khi thêm/xóa một phần tử, cập nhật freq[val] tương ứng.
  • Với mỗi truy vấn, câu trả lời là freq[compressed[X]].

Độ 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, x, 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);
    }
};

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 toàn bộ giá trị (cả a và các X trong truy vấn)
    vector<int> vals = a;
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r >> queries[i].x;
        queries[i].l--; queries[i].r--;
        queries[i].idx = i;
        vals.push_back(queries[i].x);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto get = [&](int v) {
        return lower_bound(vals.begin(), vals.end(), v) - vals.begin();
    };

    for (int i = 0; i < n; i++) a[i] = get(a[i]);
    for (int i = 0; i < q; i++) queries[i].x = get(queries[i].x);

    blockSize = max(1, (int)sqrt(n));
    sort(queries.begin(), queries.end());

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

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

    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] = freq[qr.x];
    }

    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.