概要

連続区間 \([l,r]\) の「最大値 − 最小値」がちょうど \(K\) になる区間の個数を数えます。
「差が \(K\) 以下の区間数」を高速に数えて、差が \(K-1\) 以下の区間数を引くことで答えを得ます。

考察

区間の変動幅は \(\max(A_l..A_r)-\min(A_l..A_r)\) です。これを全区間で愚直に調べると、

• 区間は全部で \(O(N^2)\) 個
• 各区間で最大・最小を求めるのに \(O(N)\)（前計算なしだと）

となり、到底間に合いません（\(N \le 2\times 10^5\)）。

ここで重要な気づきは次の2つです。

1) 「ちょうど \(K\)」は「高々 \(K\)」の差分で数えられる

「変動幅がちょうど \(K\)」の区間数を直接数えるのは難しいですが、

• \(F(D)\) = 「変動幅が \(D\) 以下（高々 \(D\)）」の区間数

とおくと、求める答えは $\( F(K) - F(K-1) \)\( になります。 なぜなら「\)K\( 以下」の中から「\)K-1\( 以下」を除くと、残るのは「ちょうど \)K$」だからです。

2) \(F(D)\) はしゃくとり法 + 単調キューで \(O(N)\) で数えられる

右端 \(r\) を固定したとき、条件 $\( \max(A_l..A_r) - \min(A_l..A_r) \le D \)\( を満たす最小の左端 \)l\( を求められれば、そこから右端 \)r\( の有効区間数は \)\( (r-l+1) \)\( 個（左端を \)l,l+1,\dots,r$ と選べる）と一気に数えられます。

ただし、区間を伸縮させるたびに最大値・最小値を取り直すと遅いので、区間内の最大・最小を「更新しながら」管理する必要があります。そこで単調キュー（deque）を使います。

アルゴリズム

1. 関数 count_at_most(A, D)：変動幅が高々 \(D\) の区間数を数える

以下を維持しながら、右端 \(r\) を左から右へ動かします。

• maxdq：区間内の最大値候補の添字を、値が 降順 になるように保つ deque
  → 先頭 maxdq[0] が現在の最大値の位置
• mindq：区間内の最小値候補の添字を、値が 昇順 になるように保つ deque
  → 先頭 mindq[0] が現在の最小値の位置
• 左端 l：条件を満たすように必要なら右へ進める

手順（各 \(r\) について）： 1. \(A[r]\) を maxdq / mindq に追加
- maxdq は末尾から「\(A[\text{末尾}] \le A[r]\)」を捨ててから \(r\) を追加
- mindq は末尾から「\(A[\text{末尾}] \ge A[r]\)」を捨ててから \(r\) を追加
こうすると deque の単調性が保たれます。 2. いまの区間 \([l,r]\) で $\( A[\text{maxdq[0]}] - A[\text{mindq[0]}] > D \)\( なら条件違反なので、左端 \)l\( を1つ進めます。 その際、もし `maxdq[0]` や `mindq[0]` がちょうど \)l\( を指していたら、区間から抜けるので先頭を `popleft()` します。 条件を満たすまでこれを繰り返します。 3. 条件を満たしたら、右端 \)r\( の有効な左端は \)l..r\( の \)(r-l+1)$ 通りなので加算します。

これで count_at_most(A, D) が \(O(N)\) で求まります。

※ \(D<0\) のとき「変動幅が \(D\) 以下」は不可能（変動幅は必ず \(\ge 0\)）なので 0 を返します。これにより \(K=0\) のケースでも $\( F(0)-F(-1)=F(0) \)$ が正しく計算できます。

2. 最終解

求める個数は $\( \text{count\_at\_most}(K) - \text{count\_at\_most}(K-1) \)$ です。

計算量

• 時間計算量: \(O(N)\)
  （各要素は maxdq と mindq に高々1回ずつ入り、高々1回ずつ出るため全体で線形）
• 空間計算量: \(O(N)\)
  （deque に添字が最大で \(N\) 個入る可能性がある）

実装のポイント

• deque には「値」ではなく「添字」を入れる（区間から抜けたかどうかを \(l\) と比較して判定するため）。

• maxdq は「降順」、mindq は「昇順」を保つように末尾を削ってから追加する。

• 条件違反時に左端を動かすとき、maxdq[0] == l / mindq[0] == l を忘れずに処理して先頭を取り除く。

• 「ちょうど \(K\)」は直接数えず、必ず「高々」の差分 \(F(K)-F(K-1)\) で数える。

  ソースコード

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

---

この解説は gpt-5.2-high によって生成されました。