概要

\(N\) 個の温度データ \(A_1, A_2, \dots, A_N\) から、最大値と最小値の差（変動幅）がちょうど \(K\) になるような連続する区間 \([l, r]\) の個数を求める問題です。

考察

1. 「ちょうど \(K\)」を言い換える

条件「変動幅がちょうど \(K\)」を直接数えるのは難しい場合があります。そこで、以下の性質を利用します。 - 変動幅が \(K\) 以上である区間の個数を \(f(K)\) とする。 - 変動幅が \(K+1\) 以上である区間の個数を \(f(K+1)\) とする。

「ちょうど \(K\)」の個数は、\(f(K) - f(K+1)\) で求めることができます。これにより、問題を「変動幅が \(X\) 以上の区間を数える」という形式に落とし込むことができます。

2. 単調性の利用と尺取り法

ある区間 \([l, r]\) の変動幅が \(X\) 以上であるとき、その区間をさらに広げた \([l, r+1]\) や \([l, r+2]\) などの変動幅も必ず \(X\) 以上になります。なぜなら、区間を広げると最大値は大きくなる（または変わらない）一方、最小値は小さくなる（または変わらない）ため、その差である変動幅は必ず広がるからです。

この「単調性」があるため、尺取り法（Two Pointers） を用いて効率的に数え上げることができます。 各左端 \(l\) に対して、変動幅が \(X\) 以上になる最小の右端 \(r\) を見つければ、右端を \(r, r+1, \dots, N\) とした全ての区間が条件を満たすことになります。

3. 区間内の最大値・最小値の取得

尺取り法で右端 \(r\) を進める際、現在の区間 \([l, r]\) 内の最大値と最小値を高速に取得する必要があります。これを実現するのが スライド最小値（最大値） のアルゴリズムで、スライド窓キュー（deque） を使用することで、要素の追加・削除を \(O(1)\) で行いながら常に区間内の最大・最小を管理できます。

アルゴリズム

1. 関数 count_ge(threshold) を定義します。これは変動幅が threshold 以上の区間数を返します。
   • \(K=0\) の場合は、全ての区間（\(\frac{N(N+1)}{2}\) 個）が条件を満たします。
2. 左端 \(l\) を \(0\) から \(N-1\) まで動かしながら、以下の操作を行います。
   • 右端 \(r\) を、区間の変動幅が threshold 以上になるまで進めます。
   • このとき、2つの deque（最大値用と最小値用）を使って、現在の区間内の最大値と最小値を管理します。
   • 条件を満たす最小の \(r\) が見つかったら、それ以降の右端（\(N-r\) 個）を合計に加算します。
   • \(l\) を次に進める前に、deque の先頭が \(l\) であれば削除します。
3. 答えを count_ge(K) - count_ge(K+1) として出力します。

計算量

• 時間計算量: \(O(N)\) count_ge 関数内では、各要素 \(A_i\) が deque に追加・削除される回数はそれぞれ高々1回です。そのため、尺取り法全体で \(O(N)\) となり、これを2回呼び出すため、全体の計算量も \(O(N)\) です。
• 空間計算量: \(O(N)\) 配列 \(A\) の保存および deque の管理に \(O(N)\) のメモリを使用します。

実装のポイント

• deque の活用: Python の collections.deque を使い、常に値が単調減少（最大値用）または単調増加（最小値用）になるようにインデックスを管理します。

• 高速な入出力: \(N=2 \times 10^5\) とデータ量が多いため、sys.stdin.read().split() や sys.stdout.write() を使用して入出力を高速化しています。

• 境界条件: \(K=0\) のとき、count_ge(0) は全区間を指し、count_ge(1) は「最大値と最小値が異なる」区間を指します。この差を取ることで、正しく「最大値と最小値が同じ（差が0）」である区間が計算されます。

  ソースコード

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()

この解説は gemini-3-flash-thinking によって生成されました。