Overview

This problem asks us to find the number of contiguous subarrays \([l, r]\) where the difference between the maximum and minimum values within the subarray is exactly \(K\). We compute “exactly \(K\)” by subtracting the count of subarrays with difference “at most \(K-1\)” from those with difference “at most \(K\)”, and each count is efficiently computed using a sliding window with monotonic deques.

Analysis

Problems with the Naive Approach

Enumerating all subarrays \([l, r]\) gives \(O(N^2)\) candidates, and computing the maximum and minimum for each leads to \(O(N^3)\) in the worst case, which is far too slow for \(N \leq 2 \times 10^5\).

Key Insight: Converting “Exactly \(K\)” to a Difference of “At Most” Counts

Directly counting the number of subarrays with a range of exactly \(K\) is difficult, but using the following relationship simplifies things:

\[f(K) = (\text{number of subarrays with range} \leq K) - (\text{number of subarrays with range} \leq K-1)\]

If we can efficiently count “the number of subarrays with range at most \(K\)”, we just call it twice and subtract.

Why the Two-Pointer Technique Works

If the range of a subarray \([l, r]\) is at most \(K\), then any sub-interval (shrinking \(r\) or increasing \(l\)) also has range at most \(K\). In other words, when \(l\) is fixed and we extend \(r\) to the right, at some point the range exceeds \(K\), and it stays exceeded from that point on. This monotonicity allows us to use the two-pointer (sliding window) technique.

Algorithm

How the Function count_at_most_k(A, N, K) Works

1. Prepare two monotonic deques:

   • max_deq: A monotonically decreasing deque to efficiently track the maximum in the window (the front holds the index of the maximum value)
   • min_deq: A monotonically increasing deque to efficiently track the minimum in the window (the front holds the index of the minimum value)

2. Advance the right endpoint \(r\) from 0 to \(N-1\):

   • Add \(A[r]\) to the deques (removing elements from the back as needed to maintain monotonicity)
   • While the range \(> K\), shift the left endpoint \(l\) one step to the right. If the front of a deque points to an index before \(l\), remove it.
   • At this point, all subarrays \([l, r], [l+1, r], \dots, [r, r]\) have range \(\leq K\), so add \(r - l + 1\) to the count.

3. The final answer is count_at_most_k(A, N, K) - count_at_most_k(A, N, K-1).

Concrete Example

For \(A = [3, 1, 4, 1, 5]\), \(K = 3\):

• Count the number of subarrays with range \(\leq 3\), count those with range \(\leq 2\), and take the difference to obtain the number of subarrays with range exactly \(3\).
• For example, the subarray \([1, 3]\) (values \(3, 1, 4\)) has maximum \(4\), minimum \(1\), range \(3\), which satisfies the condition.

Complexity

• Time complexity: \(O(N)\) (per call to count_at_most_k. Each element is added to and removed from the deque at most once. Since we call it twice, the overall complexity is also \(O(N)\))
• Space complexity: \(O(N)\) (for the deques and the input array)

Implementation Notes

• Handling the case \(K < 0\): When \(K - 1\) becomes negative, no subarray can have a range (which is always \(\geq 0\)) that is at most a negative number, so return 0.

• Store indices in the deques: By storing indices rather than values, we can remove expired elements by comparing with the left endpoint \(l\).

• Use sys.stdin.buffer.read() for fast input reading in Python.

  Source Code

import sys
from collections import deque

def count_at_most_k(A, N, K):
    """変動幅が K 以下となる連続部分配列 [l, r] の個数を数える"""
    if K < 0:
        return 0
    
    max_deq = deque()  # decreasing
    min_deq = deque()  # increasing
    left = 0
    count = 0
    
    for right in range(N):
        while max_deq and A[max_deq[-1]] <= A[right]:
            max_deq.pop()
        max_deq.append(right)
        
        while min_deq and A[min_deq[-1]] >= A[right]:
            min_deq.pop()
        min_deq.append(right)
        
        while A[max_deq[0]] - A[min_deq[0]] > K:
            left += 1
            if max_deq[0] < left:
                max_deq.popleft()
            if min_deq[0] < left:
                min_deq.popleft()
        
        count += right - left + 1
    
    return count

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    # 変動幅がちょうど K = (変動幅が K 以下) - (変動幅が K-1 以下)
    result = count_at_most_k(A, N, K) - count_at_most_k(A, N, K - 1)
    print(result)

main()

---

This editorial was generated by claude4.6opus-thinking.