Overview

Given \(N\) works, select a subsequence maintaining the original order such that the difference in evaluation scores between adjacent works is at most \(D\), and maximize the number of selected works. This is a type of conditional longest subsequence problem.

Analysis

Rephrasing the Problem

Since we select a subsequence of works while preserving the order of their indices, this is a longest subsequence problem. Specifically, from the sequence \(H_1, H_2, \ldots, H_N\), we select a subsequence such that the absolute difference between all adjacent elements is at most \(D\), and we want to find the longest such subsequence.

DP Formulation

Define \(\text{dp}[i]\) as “the maximum number of works that can be selected when work \(i\) is the last one chosen.”

The transition is as follows:

\[\text{dp}[i] = \max\left(\{\text{dp}[j] \mid j < i,\ |H_j - H_i| \leq D\}\right) + 1\]

In other words, among all works \(j\) that come before work \(i\) and have evaluation scores in the range \([H_i - D,\ H_i + D]\), find the one with the maximum \(\text{dp}[j]\) and add \(1\).

Issues with the Naive Approach

Checking all \(j < i\) for every \(i\) takes \(O(N^2)\) time, which results in TLE for \(N \leq 2 \times 10^5\).

Optimization Idea

What we need for the transition is “the maximum \(\text{dp}\) value among those whose \(H\) value falls in the range \([H_i - D, H_i + D]\).” This can be reduced to a Range Max Query.

By coordinate compressing the values of \(H\) and mapping them to segment tree indices, we can process each work from left to right:

1. Query: Retrieve the maximum value in the compressed interval corresponding to \([H_i - D, H_i + D]\)
2. Update: Write \(\text{dp}[i]\) at the position corresponding to \(H_i\)

Each operation runs in \(O(\log N)\).

Algorithm

1. Coordinate compress the values of \(H\) (sort and remove duplicates, assigning indices \(0, 1, 2, \ldots\) to each unique value).
2. Prepare a segment tree (range maximum) of size \(M\) (the number of unique values), initialized to all \(0\)s.
3. For \(i = 1, 2, \ldots, N\), do the following:
   • Using binary search, find the smallest compressed index \(lo\) that is \(\geq H_i - D\) and the largest compressed index \(hi\) that is \(\leq H_i + D\).
   • Query the segment tree for the maximum value \(\text{best}\) in the interval \([lo, hi]\).
   • Set \(\text{dp}_i = \text{best} + 1\).
   • Write \(\text{dp}_i\) at the position of \(H_i\)’s compressed index in the segment tree (update only if it is larger than the existing value).
4. The answer is the maximum of \(\text{dp}_i\) over all \(i\).

Concrete Example

For \(N=5,\ D=3,\ H=[10, 8, 12, 5, 9]\):

• Work 1 (\(H=10\)): Range \([7,13]\) has no previous works → \(\text{dp}=1\)
• Work 2 (\(H=8\)): Range \([5,11]\) contains \(H=10\) (dp=1) → \(\text{dp}=2\)
• Work 3 (\(H=12\)): Range \([9,15]\) contains \(H=10\) (dp=1) → \(\text{dp}=2\)
• Work 4 (\(H=5\)): Range \([2,8]\) contains \(H=8\) (dp=2) → \(\text{dp}=3\)
• Work 5 (\(H=9\)): Range \([6,12]\) contains \(H=8\) (dp=2), \(H=10\) (dp=1), \(H=12\) (dp=2) → \(\text{dp}=3\)

The answer is \(3\).

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for sorting in coordinate compression, and \(O(\log N)\) per work for binary search and segment tree operations)
• Space complexity: \(O(N)\) (for the segment tree and coordinate compression arrays)

Implementation Notes

• Coordinate compression: Since \(H\) values can be as large as \(10^9\), they cannot be used directly as array indices. By extracting only the unique values and compressing them, the segment tree size is kept to \(O(N)\).

• Finding the range with binary search: Using bisect_left(sorted_unique, H[i] - D) and bisect_right(sorted_unique, H[i] + D) - 1, we can precisely determine the compressed index interval corresponding to the score range \([H_i - D, H_i + D]\).

• Pruning during segment tree updates: In the update function, if the parent node’s value does not change, we terminate early to improve the constant factor.

• When \(lo > hi\): In cases where no values fall within the range, set \(\text{best} = 0\) so that \(\text{dp}_i = 1\) (selecting only that work).

  Source Code

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    D = int(input_data[1])
    H = [int(input_data[i + 2]) for i in range(N)]
    
    # dp[i] = maximum number of artworks we can select ending with artwork i
    # For each i, we want max(dp[j]) + 1 where j < i and |H[j] - H[i]| <= D
    # This means H[i] - D <= H[j] <= H[i] + D
    
    # We need an efficient way to query max dp value for H values in range [H[i]-D, H[i]+D]
    # We can use a segment tree or balanced BST with coordinate compression
    
    # Coordinate compression
    sorted_unique = sorted(set(H))
    compress = {v: idx for idx, v in enumerate(sorted_unique)}
    M = len(sorted_unique)
    
    # Segment tree for range max query, point update
    seg = [0] * (2 * M)
    
    def update(pos, val):
        pos += M
        if seg[pos] >= val:
            return
        seg[pos] = val
        while pos > 1:
            pos >>= 1
            new_val = max(seg[2 * pos], seg[2 * pos + 1])
            if seg[pos] == new_val:
                break
            seg[pos] = new_val
    
    def query(l, r):
        # query max in [l, r]
        if l > r:
            return 0
        res = 0
        l += M
        r += M + 1
        while l < r:
            if l & 1:
                res = max(res, seg[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, seg[r])
            l >>= 1
            r >>= 1
        return res
    
    import bisect
    
    ans = 0
    for i in range(N):
        h = H[i]
        # Find range of compressed indices where value is in [h-D, h+D]
        lo = bisect.bisect_left(sorted_unique, h - D)
        hi = bisect.bisect_right(sorted_unique, h + D) - 1
        
        if lo > hi:
            best = 0
        else:
            best = query(lo, hi)
        
        dp_i = best + 1
        ans = max(ans, dp_i)
        
        ci = compress[h]
        update(ci, dp_i)
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.