MảngTiền tố tổng
Mô tả
Anh Long là trưởng ban quản lý rừng Cúc Phương. Khu rừng được quy hoạch trên một dải đất dài, mỗi vị trí từ 1 đến N trồng đúng một cây gỗ. Anh Long đã đo đường kính của từng cây (tính bằng xen-ti-mét) và ghi lại thành một danh sách theo thứ tự vị trí.
Để lập hồ sơ khai thác, anh Long cần trả lời Q câu hỏi. Mỗi câu hỏi yêu cầu đếm xem trong đoạn từ vị trí L đến vị trí R (bao gồm cả hai đầu), có bao nhiêu cây gỗ có đường kính đạt từ K xen-ti-mét trở lên.
Do số lượng câu hỏi rất lớn, việc đếm từng cây cho mỗi lần hỏi sẽ mất quá nhiều thời gian. Bạn hãy giúp anh Long trả lời nhanh chóng nhé.
Đầu vào
- Dòng đầu tiên chứa hai số nguyên N và K (1 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^6).
- Dòng thứ hai chứa N số nguyên dương, số thứ i là đường kính của cây ở vị trí i (1 ≤ giá trị ≤ 10^6).
- Dòng thứ ba chứa số nguyên Q (1 ≤ Q ≤ 10^5).
- Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (1 ≤ L ≤ R ≤ N).
Đầu ra
- In ra Q dòng, mỗi dòng là số cây gỗ đạt chuẩn cho câu hỏi tương ứng.
Ràng buộc
- 1 ≤ N ≤ 10^5
- 1 ≤ Q ≤ 10^5
- 1 ≤ đường kính ≤ 10^6
- 1 ≤ K ≤ 10^6
- 1 ≤ L ≤ R ≤ N
Ví dụ
Đầu vào:
5 30 10 25 40 35 50 3 1 5 2 4 3 3
Đầu ra:
3 2 1
Giải thích:
- Cây đạt chuẩn (≥ 30cm) là cây ở vị trí 3 (40cm), vị trí 4 (35cm), vị trí 5 (50cm).
- Câu hỏi 1 (đoạn 1 đến 5): có 3 cây đạt chuẩn.
- Câu hỏi 2 (đoạn 2 đến 4): có 2 cây đạt chuẩn (vị trí 3 và 4).
- Câu hỏi 3 (đoạn 3 đến 3): có 1 cây đạt chuẩn (vị trí 3).