Diff-Query (version 1)

View as PDF



Author:
Problem types
Points: 400 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

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\).

Input

  • 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\).

Output

  • 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\).

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 10^5\).

Example

Test 1

Input
5 3
1 1 2 1 3
1 5
2 4
3 5 
Output
3
2
3

Comments


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

    "V


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

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

      1 reply