Hướng dẫn giải: Thứ Tự Phần Tử

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

Bài toán yêu cầu thực hiện 4 loại truy vấn:

1. Thêm phần tử \(X\).
2. Xóa một phần tử \(X\).
3. Tìm phần tử nhỏ thứ \(K\) hiện tại (truy vấn phần tử thứ \(K\)).
4. Đếm số lượng phần tử nhỏ hơn \(X\) (truy vấn thứ hạng - rank).

Để giải quyết bài toán này trong thời gian \(O(\log N)\), ta có thể sử dụng cấu trúc dữ liệu Indexed Skip List (Skip List có lưu độ rộng của các liên kết để cộng dồn thứ tự) hoặc một cấu trúc cây phân đoạn quản lý tần suất.

Trong C++, cách cài đặt tối ưu và nhanh chóng nhất là sử dụng GNU Policy-Based Data Structure (PBDS) với __gnu_pbds::tree. Do PBDS mặc định hoạt động như một std::set (không cho phép trùng khóa), ta giải quyết bằng cách lưu khóa dưới dạng pair<int, int> trong đó:

• Trường thứ nhất là giá trị của phần tử.
• Trường thứ hai là một mã số định danh duy nhất tăng dần theo thời gian (timer).

Các thao tác cụ thể

• Thêm \(X\): Ta gán cho \(X\) một id duy nhất và thêm {X, id} vào cây. Đồng thời lưu trữ id này vào một cấu trúc map<int, multiset<int>> để tiện quản lý.
• Xóa \(X\): Ta lấy ra id đầu tiên của \(X\) từ map và tiến hành xóa cặp {X, id} khỏi cây PBDS.
• Tìm nhỏ thứ \(K\): Sử dụng hàm find_by_order(K - 1) trong PBDS Tree.
• Đếm số lượng phần tử \(< X\): Sử dụng hàm order_of_key({X, 0}). Hàm này trả về chính xác số phần tử có khóa nhỏ hơn {X, 0}, tức là nhỏ hơn \(X\).

Độ phức tạp

• Thời gian: \(O(\log N)\) cho mỗi thao tác. Tổng thời gian là \(O((N + Q) \log N)\).
• Không gian: \(O(N)\) để lưu trữ dữ liệu trên cây.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> pbds_set;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    pbds_set s;
    int timer = 0;
    map<int, multiset<int>> ids;

    auto insert_val = [&](int x) {
        timer++;
        ids[x].insert(timer);
        s.insert({x, timer});
    };

    auto delete_val = [&](int x) {
        if (ids.count(x) && !ids[x].empty()) {
            int id = *ids[x].begin();
            ids[x].erase(ids[x].begin());
            s.erase({x, id});
        }
    };

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        insert_val(x);
    }

    for (int i = 0; i < q; i++) {
        int type, val;
        cin >> type >> val;
        if (type == 1) {
            insert_val(val);
        } else if (type == 2) {
            delete_val(val);
        } else if (type == 3) {
            int k = val;
            if (k < 1 || k > (int)s.size()) {
                cout << -1 << "\n";
            } else {
                auto it = s.find_by_order(k - 1);
                cout << it->first << "\n";
            }
        } else if (type == 4) {
            int ans = s.order_of_key({val, 0});
            cout << ans << "\n";
        }
    }
    return 0;
}