## Editorial for SAC '22 Code Challenge 4 P4 - Obligatory Subarray Problem

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: maxcruickshanks

It suffices to iterate over all subarrays while maintaining the minimum and maximum value.

For each subarray, check if the difference between the minimum and maximum value is in .

Time Complexity:

Define a function long long count(int thres) that will count the number of subarrays with a difference less than or equal to thres.

Realize that the answer is count(T) - count(B - 1) through PIE since the answer should include all answers with a difference less than or equal to , but then the answer should exclude all subarrays with a difference less than or equal to .

One way to implement count is by using a monotonic queue where the left pointer is maintained while the right pointer is incremented. Then, a counter variable is incremented by all the potential lower bound indices with PIE at each index.

Time Complexity:

Note that there are many solutions to this problem.

The bounds for are theoretically high for any solution, but all of these solutions should pass.

They were set this high to prevent a heavily constant optimized from passing.

Additionally, the author believes that distinguishing between a log factor (e.g., monotonic queue vs. sparse table) is unfair to competitors.