Tập Hợp Động Với Độ Dời Toàn Cục

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

Quản lý một đa tập các số nguyên ban đầu rỗng. Có $Q$ thao tác thuộc năm loại:

  • 1 x: Thêm $x$ vào đa tập.
  • 2 d: Cộng thêm $d$ vào tất cả các phần tử hiện có trong đa tập.
  • 3 x: Xóa một phần tử có giá trị bằng $x$ (nếu không có thì bỏ qua).
  • 4 k: In ra phần tử nhỏ thứ $k$ (đánh số từ $1$), hoặc -1 nếu không đủ phần tử.
  • 5 x: Đếm số phần tử hiện tại $\ge x$.
Dữ liệu vào
  • Dòng đầu chứa số nguyên $Q$ ($1 \le Q \le 2 \cdot 10^5$).
  • $Q$ dòng tiếp theo chứa các thao tác.
Dữ liệu ra
  • Với mỗi thao tác 4 hoặc 5, in ra kết quả trên một dòng.
Ví dụ
Input Output
8
1 5
1 10
2 3
4 1
5 10
3 8
4 1
5 20
8
1
13
0
Giới hạn
  • $1 \le Q \le 2 \cdot 10^5$, $-10^9 \le x, d \le 10^9$
Draft saved