Truy Vấn Giá Trị Phân Biệt Trong Đoạn

Buổi 75-76 — Stress Test
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho mảng gồm $N$ số nguyên $a_1, \dots, a_N$ và $Q$ truy vấn $[l, r]$. Với mỗi truy vấn, hãy đếm số lượng giá trị phân biệt xuất hiện trong đoạn con từ vị trí $l$ đến $r$.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $a_1, \dots, a_N$ ($1 \le a_i \le 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l, r$ ($1 \le l \le r \le N$).
Dữ liệu ra
  • Với mỗi truy vấn, in ra số lượng giá trị phân biệt trên một dòng.
Ví dụ
Input Output
5 3
1 2 1 3 2
1 5
1 3
2 2
3
2
1
Giới hạn
  • $1 \le N, Q \le 10^5$, $1 \le a_i \le 10^5$
Draft saved