Bài 2. Nhiên liệu (HSG THPT Nghệ An 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT Nghệ An 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một công ty vận tải là khách hàng thường xuyên của công ty kinh doanh nhiên liệu. Công ty kinh doanh nhiên liệu đã công bố giá bán nhiên liệu của ~N~ ngày sắp tới là dãy giá trị ~a_1, a_2, \ldots, a_N~. Vì là khách hàng quen nên công ty vận tải được cho chính sách ưu đãi đặc biệt như sau: Giá bán nhiên liệu ngày thứ ~i~ không lớn hơn giá bán các ngày trước đó. Như vậy nếu giá bán công bố ngày thứ ~i~ là ~a_i~ mà lớn hơn giá đã mua ở ngày thứ ~i - 1~ thì công ty vận tải sẽ được mua nhiên liệu ở ngày thứ ~i~ với giá đã mua ở ngày thứ ~i - 1~.

Để ước tính chi phí, công ty vận tải đã đưa ra ~q~ truy vấn có dạng ~L, R, x~ có nghĩa là: Trong đoạn các ngày từ ngày thứ ~L~ đến ngày thứ ~R~ có bao nhiêu ngày được mua nhiên liệu với giá ưu đãi bằng ~x~.

Dữ liệu vào

Gồm các dòng:

  • Dòng 1: Chứa số nguyên ~N (1 \le N \le 2 \times 10^5)~.
  • Dòng 2: Chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N (1 \le a_i \le 10^6)~.
  • Dòng 3: Chứa số nguyên ~q (1 \le q \le 2 \times 10^5)~.
  • ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~L, R, x (1 \le L, R \le N)~.

Kết quả

Với mỗi truy vấn, in ra số lượng ngày tìm được trên 1 dòng.

Ví dụ

Input 1

8
12 15 10 11 9 20 8 8
3
3 7 8
5 8 12
2 5 10

Output 1

1
0
2

Dãy giá ưu đãi thực tế là 12, 12, 10, 10, 9, 9, 8, 8. Truy vấn (3, 7, 8) có đúng ngày thứ 7; truy vấn (5, 8, 12) không có ngày nào; truy vấn (2, 5, 10) có ngày thứ 3 và ngày thứ 4.

Ràng buộc

  • Subtask 1 (60% số điểm): ~1 \le N, q \le 10^3~.
  • Subtask 2 (40% số điểm): ~10^3 < N, q \le 2 \times 10^5~.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...