Sắc Màu Phố Cổ

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

Phố cổ có N ngôi nhà xếp thành hàng, ngôi nhà thứ i được sơn màu c_i. Có Q câu hỏi, mỗi câu hỏi cho l, r hỏi có bao nhiêu màu khác nhau trong đoạn nhà từ l đến r.

Sử dụng thuật toán Mo để trả lời các truy vấn offline.

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q (1 ≤ N, Q ≤ 100000). Dòng thứ hai chứa N số nguyên c_1, c_2, ..., c_N (1 ≤ c_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ố lượng màu khác nhau trong đoạn [l, r] trên một dòng.

Ví dụ
Input Output
5 3\n1 2 1 3 2\n1 3\n2 5\n1 5 2\n3\n3
Giới hạn
  • 1 ≤ N, Q ≤ 100000
  • 1 ≤ c_i ≤ 100000
  • 1 ≤ l ≤ r ≤ N
Draft saved