Cấu Trúc Dữ Liệu Nâng Cao: STL Set, Map & Heap

1. Bản chất các cấu trúc dữ liệu nâng cao trong thư viện chuẩn STL

Trong lập trình thi đấu hiện đại, việc tự cài đặt lại cây nhị phân cân bằng hay bảng băm từ đầu cho mọi bài toán là không khả thi. C++ Standard Template Library (STL) cung cấp các cấu trúc dữ liệu tối ưu hóa cực mạnh:

• std::set / std::map: Cây đỏ-đen (Red-Black Tree) tự cân bằng, luôn duy trì các phần tử theo thứ tự tăng dần. Các thao tác tìm kiếm, chèn, xóa đều có độ phức tạp đảm bảo $\mathcal{O}(\log N)$.
• std::unordered_map / std::unordered_set: Bảng băm trực tiếp (Hash Table), đạt thời gian trung bình $\mathcal{O}(1)$ cho các truy vấn.
• std::priority_queue: Cấu trúc Heap nhị phân hoàn chỉnh, cho phép truy xuất phần tử lớn nhất (hoặc nhỏ nhất) trong $\mathcal{O}(1)$ và thêm/bớt trong $\mathcal{O}(\log N)$.

2. Kỹ thuật nén tọa độ (Coordinate Compression)

2.1. Bản chất bài toán & khi nào cần nén tọa độ?

• Vấn đề: Các giá trị trong mảng $A$ có thể rất lớn ($A[i] \le 10^9$ hoặc $10^{18}$), ta không thể dùng giá trị này làm chỉ số mảng đếm tần suất hoặc dựng cây Segment Tree / Fenwick Tree. Tuy nhiên, số lượng phần tử $N$ lại rất nhỏ ($N \le 10^5$).
• Nguyên lý Nén Tọa Độ: Ánh xạ tập giá trị rời rạc ban đầu về tập số nguyên liên tiếp $\{0, 1, 2, \dots, K-1\}$ ($K \le N$) sao cho giữ nguyên thứ tự tương quan lớn bé giữa các phần tử: $$A[i] < A[j] \iff \text{rank}(A[i]) < \text{rank}(A[j])$$

2.2. Quy trình 4 bước chuẩn mực trong C++

1. Sao chép mảng: vector<long long> vals = a;

2. Sắp xếp tăng dần: sort(vals.begin(), vals.end());

3. Lọc bỏ trùng lặp: vals.erase(unique(vals.begin(), vals.end()), vals.end());
4. Ánh xạ bằng Tìm kiếm nhị phân:

int compressed_val = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();

3. Hàng đợi ưu tiên (Priority Queue / heap)

• Max-Heap (Mặc định): priority_queue<long long> max_pq; $\implies$ top() trả về giá trị lớn nhất.

• Min-Heap (Đảo thứ tự): priority_queue<long long, vector<long long>, greater<long long>> min_pq; $\implies$ top() trả về giá trị nhỏ nhất.

• Ứng dụng kinh điển: Tìm $K$ phần tử lớn nhất/nhỏ nhất trong luồng dữ liệu online, thuật toán Dijkstra, thuật toán Prim, duy trì Trung vị động (Median) bằng 2 Heap.

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy Worst-case $\mathcal{O}(N)$ của unordered_map do Anti-Hash Test: * Trong các kỳ thi competitive, hàm băm mặc định std::hash của unordered_map rất dễ bị các test đối kháng (Anti-hash tests) làm tràn bucket $\implies$ Độ phức tạp tụt xuống $\mathcal{O}(N^2)$ và bị TLE. * Quy tắc an toàn: Dùng std::map khi $N \le 2 \cdot 10^5$ (đảm bảo $\mathcal{O}(N \log N)$), hoặc dùng Custom Hash an toàn với hằng số thời gian ngẫu nhiên chrono.
2. Bẫy xóa phần tử trong std::multiset: * Lệnh ms.erase(x) sẽ xóa TOÀN BỘ các phần tử có giá trị bằng $x$ trong multiset! * Cú pháp chuẩn khi chỉ muốn xóa 1 bản sao: ms.erase(ms.find(x));.
3. Bẫy truy cập map[key] tự động chèn phần tử mới: * Khi gọi if (mp[x] > 0), nếu $x$ chưa tồn tại trong map, C++ sẽ tự động chèn cặp (x, 0) vào map làm tăng kích thước bộ nhớ.

• Cú pháp an toàn: Dùng if (mp.count(x)) hoặc if (mp.find(x) != mp.end()).

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Kỹ thuật nén tọa độ chuẩn mực

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    if (n <= 0) return 0;

    vector<long long> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];

    }

    // 1. Tạo mảng nén
    vector<long long> vals = a;

    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    // 2. Ánh xạ từng phần tử
    vector<int> compressed(n);

    for (int i = 0; i < n; ++i) {
        compressed[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
    }

    for (int i = 0; i < n; ++i) {
        cout << compressed[i] << (i + 1 == n ? "" : " ");
    }
    cout << "\n";

    return 0;
}

Mẫu 2: Duy trì trung vị động bằng 2 heap (median of stream)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    if (n <= 0) return 0;

    priority_queue<long long> left_max; // Nửa nhỏ hơn (Max-Heap)

    priority_queue<long long, vector<long long>, greater<long long>> right_min; // Nửa lớn hơn (Min-Heap)

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

        if (left_max.empty() || x <= left_max.top()) {
            left_max.push(x);
        } else {
            right_min.push(x);
        }

        // Tự cân bằng kích thước: left_max luôn có size == right_min hoặc size == right_min + 1
        if (left_max.size() > right_min.size() + 1) {

            right_min.push(left_max.top());
            left_max.pop();
        } else if (right_min.size() > left_max.size()) {

            left_max.push(right_min.top());
            right_min.pop();
        }

        // In trung vị hiện tại
        cout << left_max.top() << (i + 1 == n ? "" : " ");
    }
    cout << "\n";

    return 0;
}