Bộ Sưu Tập Kỳ Lạ

Buổi 62 — Sqrt Decomposition & Mo
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Bạn có một bộ sưu tập gồm N vật phẩm xếp thành dãy, vật phẩm thứ i thuộc loại a_i. Cho số nguyên K. Có Q câu hỏi, mỗi câu hỏi cho l, r, hỏi có bao nhiêu loại vật phẩm xuất hiện đúng K lần trong đoạn [l, r].

Dữ liệu vào

Dòng đầu chứa ba số nguyên N, Q, K (1 ≤ N, 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 chứa hai số nguyên l, r (1 ≤ l ≤ r ≤ N).

Dữ liệu ra

Với mỗi truy vấn, in ra số loại vật phẩm xuất hiện đúng K lần trong đoạn [l, r].

Ví dụ
Input Output
7 3 2\n1 2 1 3 2 3 1\n1 7\n1 4\n3 6 2\n1\n1
Giới hạn
  • 1 ≤ N, Q ≤ 100000
  • 1 ≤ K ≤ N
  • 1 ≤ a_i ≤ 100000
  • 1 ≤ l ≤ r ≤ N
Draft saved