Cây Hợp Nhất Sắp Xếp
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho dãy N số nguyên dương không thay đổi. Với mỗi câu hỏi (l, r, x), hãy đếm xem trong đoạn a_l..a_r có bao nhiêu phần tử không vượt quá x. Gợi ý: mỗi nút của cây đoạn lưu danh sách đã sắp xếp của đoạn tương ứng.
Dữ liệu vào
Dòng đầu chứa N và Q. Dòng thứ hai chứa N số a_1..a_N. Q dòng tiếp theo, mỗi dòng chứa ba số l, r, x.
Dữ liệu ra
Với mỗi câu hỏi, in ra số chỉ số i ∈ [l, r] mà a_i ≤ x.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n6 6 9 3 1\n2 4 5\n3 4 3\n1 5 4\n4 4 7 | 1\n1\n2\n1 |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- 1 ≤ a_i, x ≤ 10^9
Community Discussion