Overview

While preserving the original order (by number), select some works such that the score difference between any two adjacent selected works is always at most \(D\). Find the maximum number of works that can be selected (i.e., the longest subsequence length).

Analysis

Since the selected works must remain in increasing order of their numbers (= the original array order), this is a problem of choosing a “subsequence.” The condition is that for adjacent elements \(x, y\) in the subsequence, \(|x-y|\le D\), which naturally leads to the following DP:

• \(dp[i]\): the maximum number of works when work \(i\) is chosen last.
  Then: $\( dp[i] = 1 + \max\{ dp[j] \mid j<i,\ |H_j - H_i|\le D\} \)\( (If no such \)j\( exists, then \)\max=0\( and \)dp[i]=1$.)

Naively checking all pairs \((j,i)\) results in \(O(N^2)\), which is too slow for \(N\le 2\times 10^5\) (TLE).

The key observation here is that “the \(j<i\) satisfying the condition” can be expressed as a range of values: $\(H_j \in [H_i-D,\ H_i+D]\)\( In other words, for each \)i\(, we want "the maximum \)dp$ value among past entries whose value falls within a certain interval” = this reduces to a range maximum query on the value axis.

Algorithm

1. Coordinate Compression
   Since \(H_i\) can be up to \(10^9\), we cannot use the values directly as array indices.
   Instead, sort all values of \(H\) and remove duplicates to create an array vals, then map each value to its “position in vals (0 to m-1).”

2. Speed up DP with a Segment Tree (range maximum)
   The segment tree stores “the maximum DP value among works seen so far that end with value vals[pos]” (since the same value can appear multiple times, we take the maximum).

For each work with score \(h\): - The allowed previous scores are \([h-D,\,h+D]\) - Use binary search to find the index range in vals that falls within this interval: - l = lower_bound(vals, h-D) - r = upper_bound(vals, h+D) (right end is half-open) - Execute query(l, r) on the segment tree to get the maximum DP value best in that range - dp = best + 1 - Update position idx of the current value \(h\) with dp (only if it’s larger than the existing value)

1. Answer
   The maximum dp across all steps is the answer.

Concrete Example (Illustration)

Let \(H=[10, 13, 20, 15],\ D=3\).
- 13 differs from 10 by 3, so they can be connected → length 2
- 20 needs past values in [17,23], but none exist → length 1
- 15 needs past values in [12,18], and 13 is there → connect to the length-2 sequence ending at 13, adding +1 for length 3 (specifically 10→13→15)
The role of the segment tree is to efficiently retrieve “the maximum among past entries whose value falls within an interval” at each step.

Complexity

• Time complexity: \(O(N\log M)\) (\(M\) is the number of distinct \(H_i\) values, where \(M\le N\). For each element, binary search costs \(O(\log M)\) and segment tree operations cost \(O(\log M)\).)
• Space complexity: \(O(M)\) (coordinate compression array and segment tree)

Implementation Notes

• Half-open intervals: Using bisect_left and bisect_right, and treating query(l, r) as \([l,r)\) reduces the chance of errors.

• Same value appearing multiple times: Since multiple updates can occur at the same idx, an update that “keeps only the maximum” is needed (if seg[i] >= val: return).

• Works even when \(D=0\): In this case, only works with the same value can be connected, so the range search becomes exactly a single point (an interval of equal values), and the same approach solves it.

  Source Code

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

This editorial was generated by gpt-5.2-high.