Subarrays with Bounded Maximum — Solution & Editorial

Back to the Problem

Count subarrays with max ≤ HI minus subarrays with max ≤ LO−1. For a bound B, subarrays with all elements ≤ B are counted by summing consecutive run lengths of qualifying elements.

Complexity: O(N)

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