Truy vấn thêm, xóa và trả về chênh lệch max-min trong C++

Xử lý Q truy vấn 3 loại trên một multiset:

1. 1 x: Thêm x vào tập hợp.
2. 2 x: Xóa một lần xuất hiện của x (nếu có).
3. 3: In ra max - min của tập hợp hiện tại.

Ví dụ

Q=6:
1 5  → {5}
1 9  → {5,9}
1 6  → {5,9,6}
2 4  → {5,9,6} (4 không có)
1 3  → {5,9,6,3}
3    → max=9, min=3, diff=6

Phương pháp 1: Mảng/Vector O(N) mỗi truy vấn loại 3

Duyệt tìm min/max. Chậm nếu Q lớn.

Phương pháp 2: C++ STL multiset (Cây đỏ-đen tự cân bằng) O(log N)

• Thêm: ms.insert(x)
• Xóa: ms.erase(ms.find(x)) (xóa 1 lần)
• Min: *ms.begin()
• Max: *ms.rbegin()

Chương trình C++

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

int main() {
    multiset ms;
    int Q = 6;
    vector> queries = {{1,5}, {1,9}, {1,6}, {2,4}, {1,3}, {3,0}};
    
    for (auto [type, val] : queries) {
        if (type == 1) ms.insert(val);
        else if (type == 2) {
            auto it = ms.find(val);
            if (it != ms.end()) ms.erase(it);
        } else if (type == 3) {
            if (ms.empty()) cout << "Empty\n";
            else cout << "Diff = " << (*ms.rbegin() - *ms.begin()) << endl;
        }
    }
    return 0;
}

Kết quả

Diff = 6

Độ phức tạp

Mỗi thao tác O(log N). Tổng O(Q log N). Rất hiệu quả cho Q ≤ 10⁵.