Mảng cộng dồn và truy vấn đoạn con

Mục tiêu kiến thức

• Xây dựng và sử dụng mảng cộng dồn (Prefix Sum Array) để trả lời mỗi truy vấn tổng đoạn con trong thời gian O(1).
• Kỹ thuật hai con trỏ (Two Pointers) để tìm độ dài đoạn con liên tiếp dài nhất thỏa mãn điều kiện tổng ≤ S trong thời gian O(N).
• Tối ưu hóa nhập xuất (Fast I/O) khi làm việc với dữ liệu lớn (N, Q ≤ 10⁵).
• Sử dụng kiểu dữ liệu 64-bit long long tránh tràn số khi cộng dồn.

Mô tả bài toán

Một máy chủ xử lý dữ liệu AI của AI Empire ghi nhận lượng gói tin xử lý trong N giây liên tiếp thành một dãy số nguyên không âm A₁, A₂, …, A_N (0 ≤ A_i ≤ 10⁹).

Hệ thống cần bạn giải quyết hai bài toán giám sát:

• Tìm khoảng thời gian tải ổn định: Tìm độ dài lớn nhất K của một đoạn con liên tiếp các giây [i, j] sao cho tổng lượng gói tin trong đoạn đó không vượt quá ngưỡng S cho trước: ∑_k=i^j A_k ≤ S. Nếu mọi phần tử đều lớn hơn S, độ dài lớn nhất là 0.
• Xử lý Q truy vấn kiểm tra: Cho Q truy vấn, mỗi truy vấn gồm 2 chỉ số L và R (1 ≤ L ≤ R ≤ N), hãy in ra tổng lượng gói tin từ giây thứ L đến giây thứ R: ∑_k=L^R A_k.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N, Q ≤ 10⁵.
• 0 ≤ A_i ≤ 10⁹.
• 0 ≤ S ≤ 10¹⁴.
• 1 ≤ L ≤ R ≤ N.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.