Hướng giải của [Mo's] Cặp XOR 0

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

Hai số có \(XOR = 0\) khi và chỉ khi chúng bằng nhau. Bài toán quy về đếm số cặp phần tử bằng nhau trong đoạn.

Ý tưởng:

  • Duy trì freq[val] — tần suất hiện tại.
  • Khi thêm một phần tử có giá trị \(v\) với tần suất hiện tại là \(f\):
    • Số cặp mới tạo thành là \(f\) (ghép với \(f\) phần tử đã có).
    • Tăng freq[v] lên \(1\).
  • Khi xóa một phần tử có giá trị \(v\) với tần suất hiện tại là \(f\):
    • Giảm freq[v] trước, sau đó trừ đi \(f-1\) cặp.
    • Công thức: cur_ans -= --freq[v].
  • Kết hợp: khi thêm: cur_ans += freq[v]++; khi xóa: cur_ans -= --freq[v];.

Độ 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ị
    vector<int> comp = a;
    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--;
        queries[i].idx = i;
    }
    sort(queries.begin(), queries.end());

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

    auto add = [&](int pos) { curAns += freq[a[pos]]++; };
    auto remove = [&](int pos) { curAns -= --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] = curAns;
    }

    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.