Hướng dẫn giải: Tìm Kiếm Và Thêm Phần Tử

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

Bài toán yêu cầu thực hiện hai thao tác cơ bản:

1. Thêm một giá trị \(X\) vào danh sách.
2. Tìm kiếm xem giá trị \(X\) có tồn tại trong danh sách hay không.

Cấu trúc dữ liệu Skip List (Danh sách nhảy vọt) giúp giải quyết bài toán này nhờ cơ chế danh sách liên kết đa tầng được phân bố theo xác suất (tung đồng xu):

• Tầng thấp nhất chứa toàn bộ các phần tử.
• Các tầng cao hơn đóng vai trò như các "lối tắt" (express lanes) nhảy cóc giúp bỏ qua nhanh các phần tử trung gian.
• Việc chèn và tìm kiếm trên Skip List diễn ra trong độ phức tạp thời gian trung bình (kỳ vọng) là \(O(\log N)\).

Để triển khai hiệu quả trong các kỳ thi lập trình thi đấu, ta có thể mô phỏng Skip List bằng cấu trúc cây tự cân bằng có sẵn trong thư viện chuẩn C++ là std::multiset (hoặc std::set), giúp thao tác chèn và đếm phần tử diễn ra trong thời gian \(O(\log N)\).

Độ phức tạp

• Thời gian: \(O(\log N)\) cho mỗi yêu cầu chèn và tìm kiếm. Tổng thời gian là \(O((N + Q) \log N)\).
• Không gian: \(O(N)\) bộ nhớ để lưu trữ các phần tử.

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 (s.count(x)) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
    return 0;
}