Hoàng Đế Và Tuyển Chọn
Points
90
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Đề bài
Hoàng đế có N hiệp sĩ xếp thành hàng, hiệp sĩ thứ i có cấp bậc a_i. Đôi khi hoàng đế thay đổi cấp bậc một hiệp sĩ. Hoàng đế cũng thường xuyên hỏi:
Trong đoạn hiệp sĩ từ l đến r, có bao nhiêu giá trị cấp bậc xuất hiện ít nhất K lần?
Có Q thao tác:
- Loại 1:
1 p v— thay đổi cấp bậc hiệp sĩ p thành v. - Loại 2:
2 l r— đếm số giá trị cấp bậc xuất hiện ≥ K lần trong đoạn [l, r].
Số K được cho trước.
Dữ liệu vào
Dòng đầu chứa ba số nguyên N, Q, K (1 ≤ N ≤ 100000, 1 ≤ Q ≤ 100000, 1 ≤ K ≤ N). Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N (1 ≤ a_i ≤ 100000). Q dòng tiếp theo, mỗi dòng mô tả một thao tác.
Dữ liệu ra
Với mỗi truy vấn loại 2, in ra số giá trị xuất hiện ≥ K lần trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 7 5 2\n1 2 1 3 2 3 1\n2 1 7\n1 4 1\n2 1 7\n1 7 2\n2 1 7 | 3\n2\n2 |
Giới hạn
- 1 ≤ N ≤ 100000
- 1 ≤ Q ≤ 100000
- 1 ≤ K ≤ N
- 1 ≤ a_i, v ≤ 100000
- 1 ≤ p ≤ N
- 1 ≤ l ≤ r ≤ N
Community Discussion