Overview

Given \(N\) temperature data points \(A_1, A_2, \dots, A_N\), find the number of contiguous subarrays \([l, r]\) such that the difference between the maximum and minimum values (the range of variation) is exactly \(K\).

Analysis

1. Rephrasing “exactly \(K\)”

Directly counting the condition “range of variation is exactly \(K\)” can be difficult. Instead, we use the following property: - Let \(f(K)\) be the number of subarrays whose range of variation is at least \(K\). - Let \(f(K+1)\) be the number of subarrays whose range of variation is at least \(K+1\).

The count for “exactly \(K\)” can be computed as \(f(K) - f(K+1)\). This reduces the problem to the form “count subarrays whose range of variation is at least \(X\).”

2. Monotonicity and the Two Pointers Technique

If the range of variation of a subarray \([l, r]\) is at least \(X\), then extending the subarray to \([l, r+1]\), \([l, r+2]\), etc., will also have a range of variation of at least \(X\). This is because extending the subarray can only increase (or maintain) the maximum and only decrease (or maintain) the minimum, so the difference (range of variation) never shrinks.

Due to this monotonicity, we can efficiently count using the Two Pointers technique. For each left endpoint \(l\), if we find the smallest right endpoint \(r\) such that the range of variation is at least \(X\), then all subarrays with right endpoints \(r, r+1, \dots, N\) satisfy the condition.

3. Retrieving the Maximum and Minimum Within a Subarray

As we advance the right endpoint \(r\) in the two pointers technique, we need to quickly retrieve the maximum and minimum values within the current subarray \([l, r]\). This is achieved by the sliding minimum (maximum) algorithm, which uses a sliding window deque. With this approach, we can add and remove elements in \(O(1)\) while always maintaining the maximum and minimum of the current subarray.

Algorithm

1. Define a function count_ge(threshold) that returns the number of subarrays whose range of variation is at least threshold.
   • When \(K=0\), all subarrays (\(\frac{N(N+1)}{2}\) subarrays) satisfy the condition.
2. Move the left endpoint \(l\) from \(0\) to \(N-1\), performing the following operations:
   • Advance the right endpoint \(r\) until the range of variation of the subarray reaches at least threshold.
   • Use two deques (one for the maximum, one for the minimum) to manage the maximum and minimum values within the current subarray.
   • Once the smallest \(r\) satisfying the condition is found, add \(N - r\) (the number of valid right endpoints from that point onward) to the total.
   • Before advancing \(l\) to the next position, remove the front of the deque if it equals \(l\).
3. Output the answer as count_ge(K) - count_ge(K+1).

Complexity

• Time complexity: \(O(N)\) Within the count_ge function, each element \(A_i\) is added to and removed from the deque at most once. Therefore, the entire two pointers process runs in \(O(N)\), and since we call it twice, the overall complexity is also \(O(N)\).
• Space complexity: \(O(N)\) We use \(O(N)\) memory for storing the array \(A\) and managing the deques.

Implementation Notes

• Using deques: We use Python’s collections.deque to manage indices such that the values are always monotonically decreasing (for the maximum deque) or monotonically increasing (for the minimum deque).

• Fast I/O: Since \(N = 2 \times 10^5\) and the data volume is large, we use sys.stdin.read().split() and sys.stdout.write() to speed up input and output.

• Boundary conditions: When \(K=0\), count_ge(0) refers to all subarrays, and count_ge(1) refers to subarrays where the maximum and minimum differ. Taking their difference correctly computes the number of subarrays where the maximum and minimum are the same (difference is 0).

  Source Code

import sys
from collections import deque

def solve():
    # Fast input reading: read all at once and split into a list of strings
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    # Convert all temperature values to a list of integers
    A = list(map(int, input_data[2:]))

    def count_ge(threshold):
        """
        Counts the number of continuous ranges [l, r] such that
        max(A[l...r]) - min(A[l...r]) >= threshold.
        """
        if threshold <= 0:
            # If threshold is 0 or less, every valid range [l, r] satisfies the condition.
            return N * (N + 1) // 2
        
        res = 0
        r = 0
        max_dq = deque()
        min_dq = deque()
        
        # Local variables for faster access inside the loop
        A_local = A
        N_local = N
        
        for l in range(N_local):
            # Move the right pointer r to the smallest index such that 
            # the range [l, r] satisfies the condition max - min >= threshold.
            while r < N_local:
                val_r = A_local[r]
                
                # If the current window [l, r-1] is not empty, check if adding A[r]
                # satisfies the condition.
                if max_dq:
                    mx = A_local[max_dq[0]]
                    mn = A_local[min_dq[0]]
                    
                    # Since we know the previous window [l, r-1] had max - min < threshold,
                    # the condition can only be triggered if A[r] is a new max or min.
                    if val_r - mn >= threshold or mx - val_r >= threshold:
                        break
                
                # If the condition is not yet met, add A[r] and update monotonic deques.
                while max_dq and A_local[max_dq[-1]] <= val_r:
                    max_dq.pop()
                max_dq.append(r)
                
                while min_dq and A_local[min_dq[-1]] >= val_r:
                    min_dq.pop()
                min_dq.append(r)
                
                r += 1
            
            # If the condition is satisfied for window [l, r], it is also satisfied
            # for all windows [l, r'], [l, r'+1], ..., [l, N-1].
            if r < N_local:
                res += (N_local - r)
            
            # Before moving the left pointer l to l+1, remove the index l from the deques.
            if max_dq and max_dq[0] == l:
                max_dq.popleft()
            if min_dq and min_dq[0] == l:
                min_dq.popleft()
                
        return res

    # The number of ranges where (max - min) is exactly K is:
    # (ranges with max - min >= K) - (ranges with max - min >= K + 1)
    ans = count_ge(K) - count_ge(K + 1)
    
    # Fast output
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.