Hoàng Đế Và Tuyển Chọn

Buổi 62 — Sqrt Decomposition & Mo
Points
90
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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
Draft saved