概要

連続する区間 \([l, r]\) のうち、区間内の最大値と最小値の差がちょうど \(K\) となるものの個数を求める問題です。「ちょうど \(K\)」を「\(K\) 以下」の個数から「\(K-1\) 以下」の個数を引くことで計算し、各カウントはスライディングウィンドウ＋単調デックで効率的に求めます。

考察

素朴なアプローチの問題点

すべての区間 \([l, r]\) を列挙すると \(O(N^2)\) 通りあり、それぞれで最大値・最小値を求めると最悪 \(O(N^3)\) となり、\(N \leq 2 \times 10^5\) では到底間に合いません。

重要な気づき：「ちょうど \(K\)」を「以下」の差に変換する

「変動幅がちょうど \(K\)」の個数を直接数えるのは難しいですが、次の関係を使えばシンプルになります：

\[f(K) = (\text{変動幅が } K \text{ 以下の区間数}) - (\text{変動幅が } K-1 \text{ 以下の区間数})\]

「変動幅が \(K\) 以下の区間数」を効率よく数えられれば、2回呼び出して引き算するだけです。

尺取り法が使える理由

ある区間 \([l, r]\) の変動幅が \(K\) 以下であれば、その部分区間（\(r\) を小さくする、\(l\) を大きくする）も \(K\) 以下です。つまり、\(l\) を固定したとき \(r\) を右に伸ばしていくと、ある時点から変動幅が \(K\) を超え、それ以降ずっと超えたままになります。この単調性のおかげで尺取り法（2ポインタ）が使えます。

アルゴリズム

関数 count_at_most_k(A, N, K) の動作

1. 2つの単調デックを用意する：

   • max_deq：区間内の最大値を効率的に管理する単調減少デック（先頭が最大値のインデックス）
   • min_deq：区間内の最小値を効率的に管理する単調増加デック（先頭が最小値のインデックス）

2. 右端 \(r\) を 0 から \(N-1\) まで順に進める：

   • \(A[r]\) をデックに追加（単調性を保つように末尾から不要な要素を除去）
   • 変動幅 \(> K\) の間、左端 \(l\) を1つずつ右にずらす。デックの先頭が \(l\) より左なら取り除く。
   • このとき区間 \([l, r], [l+1, r], \dots, [r, r]\) はすべて変動幅 \(\leq K\) なので、個数 \(r - l + 1\) を加算。

3. 最終的な答えは count_at_most_k(A, N, K) - count_at_most_k(A, N, K-1)。

具体例

\(A = [3, 1, 4, 1, 5]\), \(K = 3\) の場合：

• 変動幅 \(\leq 3\) の区間数を数え、変動幅 \(\leq 2\) の区間数を数え、差を取ると「変動幅がちょうど 3」の区間数が得られます。
• 例えば区間 \([1, 3]\)（値 \(3, 1, 4\)）は最大 \(4\)、最小 \(1\)、変動幅 \(3\) で条件を満たします。

計算量

• 時間計算量: \(O(N)\)（count_at_most_k 1回あたり。各要素はデックに最大1回追加・1回削除されるため。2回呼ぶので全体も \(O(N)\)）
• 空間計算量: \(O(N)\)（デックと入力配列の分）

実装のポイント

• \(K < 0\) の場合の処理: \(K - 1\) が負になる場合、変動幅（常に \(\geq 0\)）が負以下になる区間は存在しないので 0 を返す。

• デックにはインデックスを格納する: 値ではなくインデックスを入れることで、左端 \(l\) との比較で期限切れ要素を除去できる。

• sys.stdin.buffer.read() を使うことで、Python でも高速に入力を読み込める。

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。