Overview

This problem asks us to find the length of the longest subsequence such that, when arranged in order of their numbers, the difference in evaluation scores between adjacent works is at most \(D\).

Analysis

A naive approach would be dynamic programming (DP) where, for each work, we find the maximum chain length from previous works that satisfy the condition. However, this method requires \(O(N)\) computation for each work, resulting in an overall time complexity of \(O(N^2)\), which is too slow given the constraint that \(N\) can be up to \(2 \times 10^5\).

To solve this efficiently, we need to speed up the DP updates. Specifically, for each work \(i\), we need to quickly find the maximum DP value among works whose evaluation scores fall within the range \([H_i - D, H_i + D]\). Such range maximum queries can be efficiently handled using data structures like segment trees or Fenwick trees.

Algorithm

1. Dynamic Programming (DP) Setup:

   • Define \(dp[i]\) as the length of the longest subsequence ending with work \(i\).
   • For each work \(i\), update as \(dp[i] = \max\{dp[j] + 1 \mid j < i, |H_j - H_i| \leq D\}\).

2. Data Structure for Speedup:

   • Since the range of evaluation scores can be large, we first perform coordinate compression.
   • Build a segment tree that stores DP values at indices corresponding to evaluation score values.
   • For each work \(i\), use binary search to find the compressed index range corresponding to the evaluation score range \([H_i - D, H_i + D]\), then retrieve the maximum DP value from that range in the segment tree.

3. Processing Flow:

   • Perform coordinate compression on the list of evaluation scores.
   • Initialize the segment tree.
   • Process the works in order from first to last:
     • Compute the allowable range \([H_i - D, H_i + D]\) from the current work’s evaluation score \(H_i\).
     • Use binary search to find the compressed index range \([l, r]\) corresponding to this range.
     • Retrieve the maximum DP value from the range \([l, r]\) in the segment tree, and set \(dp[i] = \text{maximum value} + 1\).
     • Update the position in the segment tree corresponding to the current evaluation score with \(dp[i]\).

Complexity

• Time complexity: \(O(N \log N)\)
  • Coordinate compression: \(O(N \log N)\)
  • Processing each work: binary search and segment tree query/update are each \(O(\log N)\)
• Space complexity: \(O(N)\)
  • Segment tree: \(O(N)\)
  • DP array and compression array: \(O(N)\)

Implementation Notes

• By performing coordinate compression, the segment tree size is kept to \(O(N)\).

• The segment tree should be implemented to support range maximum queries and point updates.

• In the binary search, we need to correctly find the smallest index greater than or equal to the lower bound and the largest index less than or equal to the upper bound of the allowable range.

• When updating the segment tree, we should only update if the new value is greater than the current value (to maintain the maximum).

  Source Code

import sys

class SegmentTree:
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.data = [0] * (2 * self.size)
    
    def update(self, index, value):
        i = index + self.size
        self.data[i] = value
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def query(self, l, r):
        l += self.size
        r += self.size
        res = 0
        while l < r:
            if l % 2 == 1:
                res = max(res, self.data[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = max(res, self.data[r])
            l //= 2
            r //= 2
        return res

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    n = int(data[0])
    D = int(data[1])
    H = list(map(int, data[2:2+n]))
    
    # 座標圧縮
    sorted_H = sorted(set(H))
    comp_map = {}
    for idx, val in enumerate(sorted_H):
        comp_map[val] = idx
    comp_size = len(sorted_H)
    
    seg_tree = SegmentTree(comp_size)
    dp = [0] * n
    ans = 0
    
    for i in range(n):
        h_val = H[i]
        comp_idx = comp_map[h_val]
        low_val = h_val - D
        high_val = h_val + D
        
        # 二分探索で範囲の境界を求める
        left = 0
        right = comp_size
        # low_val以上の最小のインデックス
        l_idx = comp_size
        low = 0
        high = comp_size - 1
        while low <= high:
            mid = (low + high) // 2
            if sorted_H[mid] >= low_val:
                l_idx = mid
                high = mid - 1
            else:
                low = mid + 1
                
        # high_val以下の最大のインデックス
        r_idx = -1
        low = 0
        high = comp_size - 1
        while low <= high:
            mid = (low + high) // 2
            if sorted_H[mid] <= high_val:
                r_idx = mid
                low = mid + 1
            else:
                high = mid - 1
        
        max_val = 0
        if l_idx <= r_idx:
            max_val = seg_tree.query(l_idx, r_idx+1)
        
        dp[i] = max_val + 1
        if dp[i] > ans:
            ans = dp[i]
            
        # 現在のdp値でセグメント木を更新
        current_max = seg_tree.query(comp_idx, comp_idx+1)
        if dp[i] > current_max:
            seg_tree.update(comp_idx, dp[i])
            
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.