Subarrays with Small Product — Solution & Editorial

Back to the Problem

Sliding window on the product (positivity makes it monotone): extend right, shrink left while the product reaches K; each right endpoint adds (window length) subarrays.

Complexity: O(N)

Watch out: The count reaches ~5×10⁹ — 64-bit.