Gộp Đống Ưu Tiên
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Có $N$ hàng đợi ưu tiên (min-heap) đánh số từ $1$ đến $N$, ban đầu đều rỗng. Thực hiện $Q$ thao tác:
1 i x: Thêm số nguyên $x$ vào hàng đợi thứ $i$.2 i j: Gộp toàn bộ phần tử của hàng đợi $j$ vào hàng đợi $i$ ($i \ne j$), sau đó hàng đợi $j$ trở thành rỗng.3 i: In ra giá trị nhỏ nhất của hàng đợi $i$ (nếu rỗng inEMPTY).4 i: Xóa giá trị nhỏ nhất của hàng đợi $i$ (nếu rỗng thì bỏ qua).
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, Q$ ($1 \le N, 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 loại
3, in ra kết quả trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 3 7 1 1 10 1 2 5 2 1 2 3 1 3 2 4 1 3 1 |
5 EMPTY 10 |
Giới hạn
- $1 \le N, Q \le 2 \cdot 10^5$, $-10^9 \le x \le 10^9$
Community Discussion