Overview

Given a sequence of numbers, the problem asks to find the length of the longest subsequence (a sequence formed by selecting elements in order) such that the absolute difference between adjacent elements is at most \(D\).

Analysis

First, let’s consider a naive dynamic programming (DP) approach. Define dp[i] as “the maximum number of elements that can be selected when the \(i\)-th element is chosen last.” Then, the following recurrence holds: \(dp[i] = \max(dp[j]) + 1\) (where \(j < i\) and \(|H_i - H_j| \leq D\))

However, this method searches through all \(j\) satisfying the condition for each \(i\), resulting in \(O(N^2)\) time complexity. Given the constraint \(N \leq 2 \times 10^5\), this would exceed the time limit (TLE).

To speed this up, we consider changing the DP state from “index \(i\)” to “evaluation score \(H_i\) of the element.” When selecting the \(i\)-th element (with score \(H_i\)), the score \(H_j\) of the previously selected element must satisfy: \(H_i - D \leq H_j \leq H_i + D\) In other words, we need to efficiently find “the maximum DP value among all previously seen elements whose score is between \(H_i - D\) and \(H_i + D\).”

This can be solved using a Segment Tree, a data structure that efficiently supports “range maximum queries” and “point updates.” However, since the score \(H_i\) can be up to \(10^9\), using it directly as an array index would exceed memory limits. Therefore, we also apply a technique called coordinate compression, which extracts only the score values that appear in the input and reassigns them to smaller indices.

Algorithm

1. Coordinate Compression Create an array vals by extracting all distinct evaluation scores from \(H\) and sorting them in ascending order. This converts scores that could be up to \(10^9\) into indices ranging from \(0\) to at most \(N-1\).

2. Segment Tree Initialization Prepare a segment tree that manages range maximum values. The size should be a power of \(2\) that is at least the number of elements in vals. All initial values are \(0\).

3. DP Computation Process the elements from the 1st to the last in order. Let \(h\) be the score of the current element.

   • The score range to search is \([h - D, h + D]\).
   • Using binary search (bisect_left, bisect_right), determine which index range \([l, r]\) in vals corresponds to this score range.
   • Use the segment tree to obtain the maximum value in the range \([l, r]\). Adding \(1\) to this maximum gives dp, the maximum count when selecting the current element.
   • Update the overall answer with dp.
   • Update the position in the segment tree corresponding to \(h\) (at index bisect_left(vals, h)) with the larger of the current value and dp.

4. Output the Answer After processing all elements, output the recorded maximum value.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting for coordinate compression takes \(O(N \log N)\).
  • For each element, binary search and segment tree query/update each take \(O(\log N)\), and this is done \(N\) times, giving \(O(N \log N)\).
  • Overall, the complexity is \(O(N \log N)\), which is sufficiently fast.
• Space complexity: \(O(N)\)
  • Memory proportional to \(N\) is used for the coordinate compression array and the segment tree array.

Implementation Notes

• Non-recursive Segment Tree: In Python, function call overhead is significant, so recursive segment tree implementations can be slow. Using a bottom-up (non-recursive) implementation with a 1D array and while loops, as in the solution code, results in faster execution.

• Checking for Empty Ranges: In the range \([l, r]\) obtained by binary search, there may be cases where no scores satisfy the condition (i.e., \(l > r\)). In such cases, instead of querying the segment tree, the maximum value should be treated as \(0\).

  Source Code

import sys
from bisect import bisect_left, bisect_right

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    D = int(data[1])
    H = [int(x) for x in data[2:]]
    
    vals = sorted(list(set(H)))
    M = len(vals)
    
    size = 1
    while size < M:
        size *= 2
    
    tree = [0] * (2 * size)
    
    def query(l, r):
        l += size
        r += size
        res = 0
        while l <= r:
            if l % 2 == 1:
                if tree[l] > res:
                    res = tree[l]
                l += 1
            if r % 2 == 0:
                if tree[r] > res:
                    res = tree[r]
                r -= 1
            l //= 2
            r //= 2
        return res

    def update(pos, value):
        pos += size
        if value > tree[pos]:
            tree[pos] = value
            pos //= 2
            while pos > 0:
                left_child = tree[2 * pos]
                right_child = tree[2 * pos + 1]
                tree[pos] = left_child if left_child > right_child else right_child
                pos //= 2

    ans = 0
    for h in H:
        l = bisect_left(vals, h - D)
        r = bisect_right(vals, h + D) - 1
        
        if l <= r:
            max_val = query(l, r)
        else:
            max_val = 0
            
        dp = max_val + 1
        if dp > ans:
            ans = dp
            
        pos = bisect_left(vals, h)
        update(pos, dp)
        
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.