D-query

View as PDF
Submit solution
Points: 0.33 (partial)
Time limit: 2.25s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
© VNOI
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • -2
    Mimi  commented on June 7, 2024, 9:31 a.m.

    ai có sol cách làm chia căn k ạ? thathanks


    • 8
      Cadoc  commented on June 8, 2024, 1:26 p.m.

      bạn dùng Mo quản lý cnt[i] là số lần xuất hiện của i tại truy vấn đang xét tới á, xong cứ add và xóa như Mo bth thôi


  • -8
    chunguyen2k8  commented on Jan. 20, 2024, 12:14 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -5
      tuattsx3  commented on July 27, 2024, 1:15 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -9
      nhimthuhai  commented on Jan. 20, 2024, 4:07 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -78
    LA_NTTANH  commented on Sept. 26, 2023, 12:49 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -37
    tminh_hk20  commented on April 18, 2023, 3:12 p.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -60
      z  commented on April 18, 2023, 4:12 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -24
      thoiyen1906  commented on April 18, 2023, 3:23 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -40
      Ngumaconsi  commented on April 18, 2023, 3:20 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -32
      nthach1010  commented on April 18, 2023, 3:18 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -37
      ruby0107  commented on April 18, 2023, 3:18 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -39
      bruhlmao21  commented on April 18, 2023, 3:16 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.