概要

番号順（元の順序）を保ったまま作品をいくつか選び、隣り合う選択作品のスコア差が常に \(D\) 以下になるようにするとき、選べる最大個数（最長部分列長）を求めます。

考察

選んだ作品は必ず番号の小さい順（= 元の配列順）に並ぶので、「部分列（subsequence）」を選ぶ問題です。
条件は「部分列の隣接要素 \(x, y\) について \(|x-y|\le D\)」なので、次の DP が自然に出ます：

• \(dp[i]\)：作品 \(i\) を最後に選ぶときの最大個数
  すると
  $\( dp[i] = 1 + \max\{ dp[j] \mid j<i,\ |H_j - H_i|\le D\} \)\( （該当する \)j\( がないなら \)\max=0\( で \)dp[i]=1$）

このまま全ての \((j,i)\) を調べると \(O(N^2)\) となり、\(N\le 2\times 10^5\) では間に合いません（TLE）。

ここで重要な観察は、「\(j<i\) のうち条件を満たすもの」は 値の範囲
$\(H_j \in [H_i-D,\ H_i+D]\)\( で表せることです。つまり各 \)i\( について「過去の \)dp$ の最大値を、値がある区間に入るものだけから取りたい」= 値軸での区間最大クエリに帰着します。

アルゴリズム

1. 座標圧縮
   \(H_i\) は最大 \(10^9\) なので、そのまま配列添字にできません。
   そこで \(H\) の全ての値をソートして重複を除いた配列 vals を作り、各値を「vals 上の位置（0〜m-1）」に変換します。

2. セグメント木（区間最大）で DP を高速化
   セグメント木には、「これまでに見た作品のうち、値が vals[pos] の作品で終わる DP の最大値」を保持します（同じ値が複数回出るので最大を取る）。

各作品のスコアを \(h\) とすると、 - 許される直前スコアは \([h-D,\,h+D]\) - vals 上でこの範囲に入る添字区間を二分探索で求める
- l = lower_bound(vals, h-D) - r = upper_bound(vals, h+D)（右端は半開区間） - セグ木で query(l, r) を実行し、その範囲の最大 DP 値 best を得る - dp = best + 1 - 現在の値 \(h\) の位置 idx に dp で更新（既存より大きい場合のみ）

1. 答え
   各ステップでの dp の最大が答えです。

具体例（イメージ）

\(H=[10, 13, 20, 15],\ D=3\) とします。
- 13 は 10 と差 3 なので繋げられる → 長さ 2
- 20 は過去の [17,23] が必要だが該当なし → 長さ 1
- 15 は過去の [12,18] に 13 がある → 長さ 3 は無理で、13 までの長さ 2 に +1 して長さ 3（実際には 10→13→15）
こうした「値が区間に入る過去の最大」を毎回高速に取るのがセグ木の役割です。

計算量

• 時間計算量: \(O(N\log M)\)（\(M\) は異なる \(H_i\) の個数で \(M\le N\)。各要素につき二分探索 \(O(\log M)\) とセグ木操作 \(O(\log M)\)）
• 空間計算量: \(O(M)\)（座標圧縮配列とセグメント木）

実装のポイント

• 区間は半開区間：bisect_left と bisect_right を使い、query(l, r) は \([l,r)\) として扱うとミスが減ります。

• 同じ値が複数回出る：同じ idx へ更新が複数回起こるので、「最大だけ残す」更新（if seg[i] >= val: return）が必要です。

• \(D=0\) でも動く：この場合は「同じ値のみ繋げられる」ので、範囲検索がちょうど一点（同値の区間）になり、同じ仕組みで解けます。

  ソースコード

import sys
import bisect

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    H = list(map(int, input().split()))

    vals = sorted(set(H))
    m = len(vals)

    size = 1
    while size < m:
        size <<= 1
    seg = [0] * (2 * size)

    def update(pos, val):
        i = pos + size
        if seg[i] >= val:
            return
        seg[i] = val
        i >>= 1
        while i:
            nv = seg[i << 1]
            if seg[(i << 1) | 1] > nv:
                nv = seg[(i << 1) | 1]
            if seg[i] == nv:
                break
            seg[i] = nv
            i >>= 1

    def query(l, r):  # [l, r)
        l += size
        r += size
        res = 0
        while l < r:
            if l & 1:
                if seg[l] > res:
                    res = seg[l]
                l += 1
            if r & 1:
                r -= 1
                if seg[r] > res:
                    res = seg[r]
            l >>= 1
            r >>= 1
        return res

    ans = 0
    for h in H:
        l = bisect.bisect_left(vals, h - D)
        r = bisect.bisect_right(vals, h + D)
        best = query(l, r)
        dp = best + 1
        idx = bisect.bisect_left(vals, h)
        update(idx, dp)
        if dp > ans:
            ans = dp

    print(ans)

if __name__ == "__main__":
    main()

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