Hướng giải của Đếm Số Khác Biệt Online

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: Đếm Số Khác Biệt Online

Phân tích bài toán

Bài toán yêu cầu tính số lượng giá trị phân biệt trong một đoạn con \([l, r]\) của mảng \(A\), với điều kiện là các câu hỏi được mã hóa trực tuyến (online queries). Do đó, ta không thể sử dụng thuật toán sắp xếp câu hỏi ngoại tuyến (offline queries) kết hợp với Segment Tree / Fenwick Tree truyền thống.

Để giải quyết trực tuyến, ta sử dụng Persistent Segment Tree (Cây phân đoạn bền vững):

  • Giả sử ta duyệt qua mảng từ trái sang phải. Tại vị trí \(i\), nếu phần tử \(A_i\) đã từng xuất hiện tại vị trí cũ \(prev[A_i]\) trước đó, ta cần loại bỏ đóng góp của vị trí cũ (trừ \(1\) tại vị trí \(prev[A_i]\)) và thêm đóng góp vào vị trí mới (cộng \(1\) tại vị trí \(i\)).
  • Thay vì chỉ giữ trạng thái cuối cùng, mỗi bước \(i\) ta sẽ tạo ra một phiên bản mới của cây Segment Tree từ phiên bản cây \(i-1\). Cây phiên bản thứ \(i\) sẽ lưu thông tin số lượng phần tử khác nhau nếu ta chỉ xét tiền tố từ \(1\) đến \(i\).
  • Khi đó, để trả lời câu hỏi đếm số lượng giá trị phân biệt trong khoảng \([l, r]\) trực tuyến, ta chỉ cần truy vấn tổng đoạn \([l, r]\) trên cây phiên bản thứ \(r\).
Nén tọa độ (Coordinate Compression)

Do các giá trị đầu vào của mảng \(A_i\) có thể rất lớn (lên tới \(10^9\)), vượt quá giới hạn cấp phát của mảng đánh dấu last_pos, ta bắt buộc phải sử dụng nén tọa độ để đưa các giá trị về khoảng \([1, N]\). Vì mảng ban đầu là cố định và chỉ có các truy vấn được hỏi online, ta hoàn toàn có thể nén tọa độ tĩnh ngay từ lúc đọc mảng.

Độ phức tạp
  • Thời gian: Nén tọa độ mất \(O(N \log N)\). Xây dựng các phiên bản cây mất \(O(N \log N)\). Mỗi truy vấn được trả lời trong \(O(\log N)\). Tổng thời gian thực thi là \(O((N + Q) \log N)\), cực kỳ tối ưu.
  • Không gian: \(O(N \log N)\) nút được tạo ra trên cây.
Mã nguồn C++ tối ưu
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int left = -1, right = -1;
    int sum = 0;
};

vector<Node> tree;
vector<int> roots;

int build(int lo, int hi) {
    int id = tree.size();
    tree.push_back(Node());
    if (lo == hi) {
        return id;
    }
    int mid = lo + (hi - lo) / 2;
    int left_child = build(lo, mid);
    tree[id].left = left_child;
    int right_child = build(mid + 1, hi);
    tree[id].right = right_child;
    return id;
}

int update(int old, int lo, int hi, int pos, int val) {
    int id = tree.size();
    tree.push_back(tree[old]);
    if (lo == hi) {
        tree[id].sum += val;
        return id;
    }
    int mid = lo + (hi - lo) / 2;
    int new_left = tree[id].left;
    int new_right = tree[id].right;
    if (pos <= mid) {
        new_left = update(new_left, lo, mid, pos, val);
    } else {
        new_right = update(new_right, mid + 1, hi, pos, val);
    }
    tree[id].left = new_left;
    tree[id].right = new_right;
    tree[id].sum = tree[new_left].sum + tree[new_right].sum;
    return id;
}

int query(int id, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return tree[id].sum;
    int mid = lo + (hi - lo) / 2;
    return query(tree[id].left, lo, mid, l, r) + query(tree[id].right, mid + 1, hi, l, r);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<int> a(n + 1);
    vector<int> vals;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        vals.push_back(a[i]);
    }

    // Nén tọa độ
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
    }

    tree.reserve(n * 4 + n * 40);
    roots.push_back(build(1, n));

    vector<int> last_pos(vals.size() + 1, 0);
    for (int i = 1; i <= n; i++) {
        int val = a[i];
        int prev_root = roots.back();
        if (last_pos[val] > 0) {
            prev_root = update(prev_root, 1, n, last_pos[val], -1);
        }
        int new_root = update(prev_root, 1, n, i, 1);
        roots.push_back(new_root);
        last_pos[val] = i;
    }

    int last_ans = 0;
    for (int i = 0; i < q; i++) {
        int enc_l, enc_r;
        cin >> enc_l >> enc_r;
        int l = enc_l ^ last_ans;
        int r = enc_r ^ last_ans;
        if (l < 1 || r > n || l > r) {
            last_ans = 0;
            cout << 0 << "\n";
            continue;
        }
        last_ans = query(roots[r], 1, n, l, r);
        cout << last_ans << "\n";
    }
    return 0;
}

Nhận xét

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