D-query
Xem dạng PDF
Gửi bài giải
Điểm:
0,33 (OI)
Giới hạn thời gian:
2.25s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một dãy số ~n~ phần tử ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ và một số các truy vấn ~d~. Một truy vấn ~d~ là một cặp (~i~, ~j~) (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~). Với mỗi truy vấn ~d~(i, ~j~), bạn cần trả về số phần tử phân biệt nằm trong dãy con ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~.
Input
- Dòng ~1~: ~n~ (~1~ ~\leq~ ~n~ ~\leq~ ~30000~).
- Dòng ~2~: ~n~ số ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ (~1~ ~\leq~ ~a_{i}~ ~\leq~ ~10^{6}~).
- Dòng ~3~: ~q~ (~1~ ~\leq~ ~q~ ~\leq~ ~200000~), số lượng truy vấn- ~d~.
- Trong ~q~ dòng sau, mỗi dòng chứa ~2~ số ~i~, ~j~ biểu thị một truy vấn-d (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~).
Output
- Với mỗi truy vấn ~d~(~i~, ~j~), in ra số phần tử phân biệt thuộc dãy con ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~ trên một dòng.
Sample Input
5
1 1 2 1 3
3
1 5
2 4
3 5
Sample Output
3
2
3
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.