Đếm số giá trị phân biệt trong đoạn

Buổi 30 — Persistent Segment Tree
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho dãy $a_1,\dots,a_n$. Với mỗi truy vấn $(l,r)$ hãy đếm số giá trị phân biệt xuất hiện trong $a_l,\dots,a_r$. Yêu cầu trả lời trực tuyến.

Dữ liệu vào

Dòng đầu: $n,q$. Dòng hai: $n$ số nguyên dương. Tiếp theo $q$ dòng: $l,r$.

Dữ liệu ra

Với mỗi truy vấn in số giá trị phân biệt.

Ví dụ

Input

5 5
2 3 3 2 2
4 5
3 3
1 3
3 3
2 4

Output

1
1
2
1
2
Giới hạn
  • $1\le n,q\le 10^5$; $1\le a_i\le 10^9$.
  • Thời gian: 2 giây; bộ nhớ: 256 MB.
Draft saved