Cây Hợp Nhất Sắp Xếp

Buổi 27 — Segment Tree cơ bản
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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
Draft saved