Tập hợp động phần tử thứ K

Binary-search Buổi 26 — Fenwick Tree Data-structures
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Ban đầu có một tập hợp rỗng (cho phép chứa các phần tử trùng nhau). Thực hiện $Q$ truy vấn:

  • 1 x: Thêm một phần tử có giá trị $x$ vào tập hợp ($1 \le x \le 2 \cdot 10^5$).
  • 2 x: Xóa một phần tử có giá trị $x$ khỏi tập hợp (nếu $x$ không có trong tập, bỏ qua).
  • 3 k: Tìm phần tử nhỏ thứ $k$ (1-indexed) trong tập hợp hiện tại. Nếu tập có ít hơn $k$ phần tử, in ra -1.
Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $Q$ ($1 \le Q \le 2 \cdot 10^5$).
  • $Q$ dòng tiếp theo mô tả các truy vấn.
Dữ liệu ra
  • Với mỗi truy vấn loại 3, in ra kết quả trên một dòng.
Ví dụ
Input Output
7
1 5
1 2
1 5
3 2
2 5
3 2
3 3
5
5
-1
Giới hạn
  • $1 \le Q \le 2 \cdot 10^5, 1 \le x \le 2 \cdot 10^5$
Draft saved