Count Subarrays with Fixed Bounds
Quite an elegant solution once you realise the observation.
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
/*
for i..j
observation: you can iterate for all j s.t. nums[j] = maxK
now say l is 0, use dq to find the range minimum and then pop till
range min condition is invalid
in this case [dq front, front + 1) would be the valid range of left start
note you would need a min deque and a max deque as the nums[j] can be minK as well
^ actually this is incomplete and half baked
OR
minI = max i so far s.t. nums[i] = minK,
similarly maxI
badI = max i so far s.t. num[i] is outside range
*/
long long ans = 0;
int n = nums.size();
int minI = -1, maxI = -1, badI = -1;
for (int i = 0; i < n; i++) {
if (nums[i] == minK) minI = i;
if (nums[i] == maxK) maxI = i;
if (nums[i] < minK || nums[i] > maxK) badI = i;
int start = badI + 1;
int end = min(minI, maxI);
if (end != -1 && end >= start) ans += (end - start + 1);
}
return ans;
}