Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
Let <code>p[i]</code> be whether <code>nums[i]</code> is a peak in the original array. Namely <code>p[i] = nums[i] > nums[i - 1] && nums[i] > nums[i + 1]</code>.
Updating <code>nums[i]</code>, only affects <code>p[i]</code>, <code>p[i - 1]</code> and <code>p[i + 1]</code>. We can recalculate the 3 values in constant time.
The answer for <code>[l<sub>i</sub>, r<sub>i</sub>]</code> is <code>p[l<sub>i</sub> + 1] + p[l<sub>i</sub> + 2] + … + p[r<sub>i</sub> - 1]</code> (note that <code>l<sub>i</sub></code> and <code>r<sub>i</sub></code> are not included).
Use some data structures (i.e. segment tree or binary indexed tree) to maintain the subarray sum efficiently.
Solve with full IDE support and test cases