Subtask 1

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 ~[B, T]~.

Time Complexity: ~\mathcal{O}(N^2)~

Subtask 2

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 ~T~, but then the answer should exclude all subarrays with a difference less than or equal to ~B-1~.

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: ~\mathcal{O}(N)~

Note that there are many solutions to this problem.

The bounds for ~N~ are theoretically high for any ~\mathcal{O}(N \log N)~ solution, but all of these solutions should pass.

They were set this high to prevent a heavily constant optimized ~\mathcal{O}(N^2)~ from passing.

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