Hướng giải của [Mo's] Phổ Biến

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 phần tử xuất hiện nhiều nhất (mode) trong đoạn. Sử dụng Mo's Algorithm kết hợp mảng tần suất và mảng đếm tần suất.

Ý tưởng:

  • Duy trì freq[val] — tần suất của từng giá trị.
  • Duy trì freqOfFreq[cnt] — số lượng giá trị có tần suất đúng bằng \(cnt\).
  • Duy trì maxFreq — tần suất lớn nhất hiện tại.
  • Khi thêm một phần tử: giảm freqOfFreq[freq[val]], tăng freq[val], tăng freqOfFreq[freq[val]], cập nhật maxFreq.
  • Khi xóa: ngược lại.
  • Để tìm giá trị nhỏ nhất khi hòa, duyệt từ nhỏ đến lớn để tìm giá trị đầu tiên có tần suất bằng maxFreq. Tối ưu bằng cách lưu thêm một mảng phụ.

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

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ị và lưu bảng ánh xạ ngược
    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));
    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> freqOfFreq(n + 1, 0);
    int maxFreq = 0, curL = 0, curR = -1;

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

    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--);
        // Tìm giá trị nhỏ nhất có tần suất = maxFreq
        for (int v = 0; v < m; v++) {
            if (freq[v] == maxFreq) {
                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.