Diff-Query (version 1)
Xem PDF
Điểm:
400 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
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
Bình luận
"V
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.