Hướng giải của [Mo's] Trung Vị

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 tìm trung vị động trên đoạn. Sử dụng Mo's Algorithm kết hợp kỹ thuật chia căn trên miền giá trị.

Ý tưởng:

  • Duy trì mảng tần suất freq[val] và mảng blockFreq — tần suất theo khối giá trị (kích thước \(\sqrt{maxVal}\)).
  • Khi thêm/xóa phần tử: cập nhật freq và blockFreq trong \(O(1)\).
  • Với mỗi truy vấn, tìm phần tử thứ \(k\) (\(k = \lfloor (len+1)/2 \rfloor\)):
    • Duyệt qua các khối giá trị, trừ dần \(k\) cho đến khi tìm được khối chứa trung vị.
    • Duyệt trong khối đó để tìm giá trị cụ thể.
    • Độ phức tạp \(O(\sqrt{maxVal})\) mỗi truy vấn.

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

Mã nguồn C++

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

int blockSize, valBlockSize, maxVal;
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);
    }
};

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;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int m = comp.size();
    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));
    valBlockSize = max(1, (int)sqrt(m));
    int numValBlocks = (m + valBlockSize - 1) / valBlockSize;

    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].l--; queries[i].r--;
        queries[i].idx = i;
    }
    sort(queries.begin(), queries.end());

    vector<int> ans(q);
    vector<int> freq(m, 0);
    vector<int> valBlockFreq(numValBlocks, 0);
    int curL = 0, curR = -1, total = 0;

    auto add = [&](int pos) {
        int v = a[pos];
        if (freq[v] == 0) valBlockFreq[v / valBlockSize]++;
        freq[v]++;
        total++;
    };
    auto remove = [&](int pos) {
        int v = a[pos];
        freq[v]--;
        if (freq[v] == 0) valBlockFreq[v / valBlockSize]--;
        total--;
    };

    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--);

        int k = (total + 1) / 2; // vị trí trung vị (1-indexed)
        int cur = 0, blockIdx = 0;
        // Tìm khối chứa trung vị
        while (cur + valBlockFreq[blockIdx] < k) {
            cur += valBlockFreq[blockIdx];
            blockIdx++;
        }
        // Tìm trong khối
        int start = blockIdx * valBlockSize;
        int end = min(m, start + valBlockSize);
        for (int v = start; v < end; v++) {
            cur += freq[v];
            if (cur >= k) {
                ans[qr.idx] = comp[v];
                break;
            }
        }
    }

    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.