#5230. Đếm số giá trị phân biệt trong đoạn (Mã bài: DQUERY)

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một dãy a gồm n số nguyên. Bạn cần trả lời q truy vấn, mỗi truy vấn cho bởi hai chỉ số i j . Yêu cầu là đếm số lượng giá trị phân biệt trong đoạn con a[i..j] của dãy.

Dữ liệu:

  • Dòng đầu tiên chứa số nguyên n ( 1 \le n \le 30000 ).
  • Dòng thứ hai chứa n số nguyên của dãy a ( 1 \le a_i \le 10^6 ).
  • Dòng thứ ba chứa số nguyên q ( 1 \le q \le 200000 ).
  • q dòng tiếp theo, mỗi dòng chứa hai số nguyên i, j ( 1 \le i \le j \le n ).

Kết quả: Với mỗi truy vấn, in ra câu trả lời trên một dòng riêng.

Ví dụ:

Dữ liệu:

6
1 1 2 1 3 2
3
1 5
2 6
3 3

Kết quả:

3
3
1