Diff-Query (version 1)

View as PDF

Submit solution

Points: 400 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Author:
Problem types

Cho dãy số ~A~ gồm ~N~ phần tử gồm các số nguyên dương ~A_1, A_2, ..., A_N~, và ~Q~ truy vấn, truy vấn thứ ~i~ gồm ~2~ số nguyên dương ~L_i, R_i~ ~(1 \leq L_i \leq R_i \leq N)~.

Yêu cầu: Với mỗi truy vấn thứ ~i~, hãy đếm số phần tử phân biệt trong khoảng từ ~L_i~ tới ~R_i~.

Dữ liệu vào: Gồm ~Q+2~ dòng:

  • Dòng thứ nhất chứa hai số nguyên dương ~N, Q~.
  • Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ ~(1 \leq A_i \leq 10^6)~.
  • ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~L_i, R_i~.

Kết quả: In ra ~Q~ dòng, dòng thứ ~i~ là số phần tử phân biệt trong khoảng từ ~L_i~ tới ~R_i~.

Ràng buộc:

  • ~50~% số test đầu tiên tương ứng với ~50~% số điểm có ~N, Q \leq 10^3~.
  • ~50~% số test còn lại tương ứng với ~50~% số điểm có ~N, Q \leq 10^5~.

Ví dụ:

Input:

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

Output:

3
2
3

View comments (5)

Comments


  • 0
    algorit  commented on 3:47 p.m. 11 aug, 2020 edited

    "V


  • -5
    vinhntndu  commented on 9:34 a.m. 11 aug, 2020

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 0
      hhoangcpascal  commented on 2:37 p.m. 16 aug, 2020

      Bài này lm tiên đề cho bài sau :3


      • 0
        vinhntndu  commented on 10:12 a.m. 17 aug, 2020

        bỏ đê mà làm người bạn êy :V