Hướng giải của Tìm MEX Trên Khoảng 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: Tìm MEX Trên Khoảng Online

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

Yêu cầu tìm MEX (số nguyên không âm nhỏ nhất chưa xuất hiện) trong khoảng \(A[l..r]\) của dãy số trực tuyến (online). Do chiều dài dãy số là \(N\), giá trị MEX lớn nhất có thể đạt được là \(N+1\). Bất kỳ giá trị nào \(> N\) trong mảng đều có thể coi như \(N+1\) mà không làm ảnh hưởng đến kết quả MEX.

Ta sử dụng Persistent Segment Tree (Cây phân đoạn bền vững) quản lý các giá trị từ \(0\) đến \(N+1\):

  • Phiên bản cây thứ \(i\) đại diện cho trạng thái của mảng sau khi duyệt đến phần tử \(A_i\).
  • Ở phiên bản thứ \(i\), mỗi lá quản lý giá trị \(v\) sẽ lưu trữ vị trí xuất hiện cuối cùng của giá trị \(v\) trong tiền tố \(A[1..i]\).
  • Các nút cha quản lý khoảng giá trị \([lo, hi]\) sẽ lưu giá trị nhỏ nhất của các vị trí xuất hiện cuối cùng của tất cả các giá trị thuộc khoảng đó (min_pos).
Cập nhật & Truy vấn
  • Cập nhật: Khi duyệt đến phần tử \(A_i\), ta tạo ra phiên bản cây thứ \(i\) bằng cách cập nhật lá quản lý giá trị \(A_i\) có vị trí xuất hiện cuối cùng thành \(i\).
  • Truy vấn MEX trên \([l, r]\): Sử dụng cây phiên bản thứ \(r\). Ta cần tìm giá trị \(v\) nhỏ nhất sao cho vị trí xuất hiện cuối cùng của nó \(< l\). Nhờ thuộc tính min_pos được lưu ở mỗi nút:
    • Nếu con trái có min_pos < l, chứng tỏ tồn tại ít nhất một giá trị \(v\) ở nhánh trái chưa xuất hiện trong đoạn \([l, r]\). Do đó ta chắc chắn đi sang nhánh trái.
    • Ngược lại, tất cả giá trị ở nhánh trái đều đã xuất hiện từ lượt \(l\) trở đi, ta bắt buộc phải đi sang nhánh phải.
    • Khi đi đến nút lá, chỉ số của lá chính là kết quả MEX cần tìm.
Độ phức tạp
  • Thời gian: Xây dựng cây ban đầu mất \(O(N)\). Mỗi thao tác cập nhật và truy vấn MEX diễn ra trong \(O(\log N)\). Tổng thời gian xử lý là \(O((N + Q) \log N)\).
  • Không gian: \(O(N \log N)\) do mỗi bước cập nhật sinh thêm \(O(\log N)\) nút.
Mã nguồn C++ tối ưu
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int left = -1, right = -1;
    int min_pos = 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 val_node, int pos) {
    int id = tree.size();
    tree.push_back(tree[old]);
    if (lo == hi) {
        tree[id].min_pos = pos;
        return id;
    }
    int mid = lo + (hi - lo) / 2;
    int new_left = tree[id].left;
    int new_right = tree[id].right;
    if (val_node <= mid) {
        new_left = update(new_left, lo, mid, val_node, pos);
    } else {
        new_right = update(new_right, mid + 1, hi, val_node, pos);
    }
    tree[id].left = new_left;
    tree[id].right = new_right;
    tree[id].min_pos = min(tree[new_left].min_pos, tree[new_right].min_pos);
    return id;
}

int query_mex(int id, int lo, int hi, int l) {
    if (lo == hi) {
        return lo;
    }
    int mid = lo + (hi - lo) / 2;
    int left_child = tree[id].left;
    if (tree[left_child].min_pos < l) {
        return query_mex(left_child, lo, mid, l);
    } else {
        return query_mex(tree[id].right, mid + 1, hi, l);
    }
}

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);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > n) a[i] = n + 1;
    }

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

    for (int i = 1; i <= n; i++) {
        int new_root = update(roots.back(), 0, max_val, a[i], i);
        roots.push_back(new_root);
    }

    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_mex(roots[r], 0, max_val, l);
        cout << last_ans << "\n";
    }
    return 0;
}

Nhận xét

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