Truy vấn phần tử nhỏ thứ K trong tập động

Buổi 31 — Policy-Based DS
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Ban đầu bạn có một tập hợp rỗng $S$ (không chứa phần tử trùng lặp). Bạn cần thực hiện $Q$ truy vấn thuộc ba loại sau:

  • 1 x: Thêm số nguyên $x$ vào tập $S$ (nếu $x$ đã có trong $S$ thì không làm gì).
  • 2 x: Xóa số nguyên $x$ khỏi tập $S$ (nếu $x$ không có trong $S$ thì không làm gì).
  • 3 k: In ra phần tử nhỏ thứ $k$ trong tập $S$ (đánh số từ $1$). Nếu tập $S$ 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 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn dạng 1 x, 2 x ($|x| \le 10^9$) hoặc 3 k ($1 \le k \le 10^5$).
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
8
1 10
1 5
1 10
3 1
3 2
3 3
2 5
3 1
5
10
-1
10
Giới hạn
  • $1 \le Q \le 10^5$
  • $|x| \le 10^9$
  • $1 \le k \le 10^5$
Draft saved