Editorial for Tổng đoạn con

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

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]~.

Độ phức tạp: $O(n.log(n))$ ~O(n.log(n))~.

Editorial for Tổng đoạn con

Comments