Overview

Count the number of contiguous subarrays \([l,r]\) where “maximum − minimum” is exactly \(K\). We obtain the answer by efficiently counting “the number of subarrays with difference at most \(K\)” and subtracting “the number of subarrays with difference at most \(K-1\)”.

Analysis

The range of a subarray is \(\max(A_l..A_r)-\min(A_l..A_r)\). If we naively check all subarrays:

• There are \(O(N^2)\) subarrays in total
• Finding the max and min of each subarray takes \(O(N)\) (without preprocessing)

This is far too slow (\(N \le 2\times 10^5\)).

The key observations are the following two:

1) “Exactly \(K\)” can be counted using the difference of “at most \(K\)”

Directly counting subarrays with range exactly \(K\) is difficult, but if we define:

• \(F(D)\) = the number of subarrays with range at most \(D\)

then the desired answer is $\( F(K) - F(K-1) \)\( This is because removing "at most \)K-1\(" from "at most \)K\(" leaves exactly "exactly \)K$“.

2) \(F(D)\) can be computed in \(O(N)\) using the two-pointer technique + monotonic deques

If we fix the right endpoint \(r\) and find the smallest left endpoint \(l\) such that $\( \max(A_l..A_r) - \min(A_l..A_r) \le D \)\( then the number of valid subarrays ending at \)r\( is \)\( (r-l+1) \)\( (since the left endpoint can be chosen as \)l,l+1,\dots,r$), which can be counted all at once.

However, recomputing the maximum and minimum each time the window expands or shrinks would be slow, so we need to maintain the max and min of the window incrementally. For this, we use monotonic deques.

Algorithm

1. Function count_at_most(A, D): Count the number of subarrays with range at most \(D\)

We move the right endpoint \(r\) from left to right while maintaining:

• maxdq: A deque storing indices of maximum value candidates in the window, kept in descending order of values → The front maxdq[0] holds the position of the current maximum
• mindq: A deque storing indices of minimum value candidates in the window, kept in ascending order of values → The front mindq[0] holds the position of the current minimum
• Left endpoint l: Advanced to the right as needed to satisfy the condition

Steps (for each \(r\)): 1. Add \(A[r]\) to maxdq / mindq - For maxdq, remove elements from the back while “\(A[\text{back}] \le A[r]\)”, then append \(r\) - For mindq, remove elements from the back while “\(A[\text{back}] \ge A[r]\)”, then append \(r\) This preserves the monotonicity of the deques. 2. If the current window \([l,r]\) satisfies $\( A[\text{maxdq[0]}] - A[\text{mindq[0]}] > D \)\( then the condition is violated, so we advance the left endpoint \)l\( by one. At that point, if `maxdq[0]` or `mindq[0]` points exactly to \)l\(, it leaves the window, so we `popleft()` from the front. Repeat this until the condition is satisfied. 3. Once the condition is satisfied, the number of valid left endpoints for right endpoint \)r\( is \)(r-l+1)$, so we add this to the total.

This computes count_at_most(A, D) in \(O(N)\).

※ When \(D<0\), “range at most \(D\)” is impossible (since the range is always \(\ge 0\)), so we return 0. This ensures that even when \(K=0\), $\( F(0)-F(-1)=F(0) \)$ is computed correctly.

2. Final Answer

The desired count is $\( \text{count\_at\_most}(K) - \text{count\_at\_most}(K-1) \)$

Complexity

• Time complexity: \(O(N)\) (Each element enters and leaves maxdq and mindq at most once each, so the total work is linear)
• Space complexity: \(O(N)\) (The deques may hold up to \(N\) indices)

Implementation Notes

• Store indices rather than values in the deques (so we can check whether an element has left the window by comparing with \(l\)).

• Remove elements from the back before appending to maintain maxdq in “descending” order and mindq in “ascending” order.

• When advancing the left endpoint due to a condition violation, don’t forget to check maxdq[0] == l / mindq[0] == l and remove the front element accordingly.

• Never count “exactly \(K\)” directly; always use the difference of “at most” values: \(F(K)-F(K-1)\).

  Source Code

import sys
from collections import deque

def count_at_most(A, D):
    if D < 0:
        return 0
    maxdq = deque()
    mindq = deque()
    l = 0
    ans = 0
    for r, x in enumerate(A):
        while maxdq and A[maxdq[-1]] <= x:
            maxdq.pop()
        maxdq.append(r)
        while mindq and A[mindq[-1]] >= x:
            mindq.pop()
        mindq.append(r)

        while A[maxdq[0]] - A[mindq[0]] > D:
            if maxdq[0] == l:
                maxdq.popleft()
            if mindq[0] == l:
                mindq.popleft()
            l += 1
        ans += r - l + 1
    return ans

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    A = data[2:2+N]
    res = count_at_most(A, K) - count_at_most(A, K - 1)
    print(res)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.