Hướng giải: Tổng đoạn con

Tác giả: Yunan (Master) đăng lúc 24/07/2026 15:04

Tổng đoạn con

Mã bài: binarysearch08 Nhóm: Uncategorized Điểm: 2.000 điểm

Xem đề

Giới hạn: 1,0 s, 256 MB
Tỉ lệ AC: 25,4%
Người giải: 11

Chỉ đọc hướng giải khi bế tắc và đừng sao chép mã trong đó. Hãy tôn trọng người ra đề và người viết hướng giải: nộp lời giải chính thức khi chưa tự giải được bài có thể khiến bạn bị khóa tài khoản.

Với mỗi vị trí $j$ ~j~ $(1 \le j \le n)$ ~(1 \le j \le n)~, ta đếm số đoạn con $[i,j]$ ~[i,j]~ $(1 \le i \le j)$ ~(1 \le i \le j)~ thỏa mãn bài toán. Tiến hành tìm chỉ số $k$ ~k~ nhỏ nhất thỏa mãn $a_k+a_{k+1}+...+a_j \le S$ ~a_k+a_{k+1}+...+a_j \le S~ thông qua Tìm kiếm nhị phân (Binary Search) kết hợp Tổng tiền tố (Prefix Sum). Khi đó các chỉ số $i$ ~i~ thỏa mãn tổng các phần tử đoạn $[i,j]$ ~[i,j]~ không vượt quá $S$ ~S~ sẽ nằm trong đoạn $[k,j]$ ~[k,j]~.