Hướng dẫn giải: Tìm Số Kế Cận

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

Yêu cầu quản lý một tập hợp đa tập (cho phép trùng lặp phần tử) và hỗ trợ tìm:

1. Giá trị lớn nhất mà nhỏ hơn \(X\) (predecessor).
2. Giá trị nhỏ nhất mà lớn hơn \(X\) (successor).

Đây là hai thao tác tìm kiếm kế cận kinh điển trên cấu trúc dữ liệu Skip List. Trên Skip List, để tìm predecessor của \(X\), ta chỉ cần duyệt từ trên xuống dưới, nhảy sang phải cho đến khi gặp giá trị \(\ge X\), lúc đó phần tử đứng ngay trước chính là predecessor. Thao tác tương tự cho successor.

Trong C++, chúng ta có thể mô phỏng lại Skip List một cách đơn giản bằng std::multiset và các hàm tìm kiếm nhị phân được tối ưu hóa:

• Predecessor của \(X\): Gọi lower_bound(X). Iterator trả về vị trí phần tử đầu tiên \(\ge X\). Do đó, phần tử nằm ngay trước nó (nếu tồn tại) chính là phần tử lớn nhất \(< X\).
• Successor của \(X\): Gọi upper_bound(X). Iterator trả về vị trí phần tử đầu tiên \(> X\), đó chính là giá trị nhỏ nhất lớn hơn \(X\).

Độ phức tạp

• Thời gian: \(O(\log N)\) cho mỗi thao tác thêm, xóa và tìm kiếm kế cận.
• Không gian: \(O(N)\) để lưu trữ dữ liệu.

Mã nguồn C++ mẫu

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    multiset<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    for (int i = 0; i < q; i++) {
        int type, x;
        cin >> type >> x;
        if (type == 1) {
            s.insert(x);
        } else if (type == 2) {
            auto it = s.find(x);
            if (it != s.end()) {
                s.erase(it);
            }
        } else if (type == 3) {
            auto it = s.lower_bound(x);
            if (it == s.begin()) {
                cout << -1 << "\n";
            } else {
                cout << *(--it) << "\n";
            }
        } else if (type == 4) {
            auto it = s.upper_bound(x);
            if (it == s.end()) {
                cout << -1 << "\n";
            } else {
                cout << *it << "\n";
            }
        }
    }
    return 0;
}