Quản lý đa tập hợp số nguyên động

Mục tiêu kiến thức

• Sử dụng cấu trúc Cây đỏ đen cân bằng std::multiset trong C++ để lưu trữ tập hợp có phần tử trùng nhau.
• Phân biệt thao tác xóa một bản sao duy nhất (s.erase(s.find(x))) và xóa toàn bộ các phần tử có giá trị bằng X (s.erase(x)).
• Sử dụng phương thức thành viên s.lower_bound(x) với độ phức tạp O(log N).
• Kỹ thuật dịch chuyển iterator bằng std::prev() để tìm phần tử lớn nhất ≤ X.

Mô tả bài toán

Hệ thống sàn giao dịch thẻ bài huấn luyện AI của AI Empire Academy quản lý một kho dữ liệu chứa các giá trị sức mạnh của các thẻ bài. Kho dữ liệu bắt đầu với trạng thái rỗng.

Bạn cần xử lý lần lượt Q truy vấn thuộc 4 loại sau (1 ≤ Q ≤ 10⁵):

• 1 X: Thêm một thẻ bài có giá trị X vào kho.
• 2 X: Xóa đúng một thẻ bài có giá trị X khỏi kho (nếu trong kho có nhiều thẻ bài giá trị X, chỉ xóa 1 bản sao; nếu không có thẻ bài nào giá trị X, bỏ qua thao tác này).
• 3 X: Tìm cận trên: Tìm và in ra giá trị thẻ bài nhỏ nhất trong kho có giá trị ≥ X. Nếu kho không có thẻ bài nào ≥ X, in -1.
• 4 X: Tìm cận dưới: Tìm và in ra giá trị thẻ bài lớn nhất trong kho có giá trị ≤ X. Nếu kho không có thẻ bài nào ≤ X, in -1.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ Q ≤ 10⁵.
• -10⁹ ≤ X ≤ 10⁹.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.