<p>You are given an integer array <code>nums</code> and an integer <code>k</code>.</p>

<p>Find the longest subsequence of <code>nums</code> that meets the following requirements:</p>

<ul>
	<li>The subsequence is <strong>strictly increasing</strong> and</li>
	<li>The difference between adjacent elements in the subsequence is <strong>at most</strong> <code>k</code>.</li>
</ul>

<p>Return<em> the length of the <strong>longest</strong> <strong>subsequence</strong> that meets the requirements.</em></p>

<p>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,2,1,4,3,4,5,8,15], k = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong>
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,4,5,1,8,12,4,7], k = 5
<strong>Output:</strong> 4
<strong>Explanation:</strong>
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5], k = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong>
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], k &lt;= 10<sup>5</sup></code></li>
</ul>

from typing import List
import bisect
import math

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

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        dp = [1]*n
        
        # Coordinate Compression
        unique_nums = sorted(set(nums))
        num_to_idx = {num:idx+1 for idx, num in enumerate(unique_nums)}  # 1-based indexing
        
        # Initialize Segment Tree
        st = SegmentTree(len(unique_nums))
        
        max_length =1
        
        for i in range(n):
            current_num = nums[i]
            lower_num = current_num -k
            
            # Find the smallest index where num >= lower_num
            left = bisect.bisect_left(unique_nums, lower_num)
            # Find the largest index where num < current_num
            right = bisect.bisect_left(unique_nums, current_num) -1
            
            if right >= left:
                max_prev_dp = st.query(left+1, right+1)  # +1 for 1-based indexing
                dp[i] = max_prev_dp +1
            else:
                dp[i] =1  # Start a new subsequence
            
            # Update the Segment Tree with dp[i] at current_num's index
            st.update(num_to_idx[current_num], dp[i])
            
            # Update the global maximum
            if dp[i] > max_length:
                max_length = dp[i]
        
        return max_length

38200