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

class SegmentTree:
    def __init__(self, max_num):
        self.max_num = max_num
        self.tree = [0] * (self.max_num * 4)

    def get_indices(self, node, start, end):
        mid = (start + end) // 2
        left_node = node * 2 + 1
        right_node = node * 2 + 2
        return mid, left_node, right_node

    def query_max(self, node, start, end, left, right):
        if left > end or right < start:
            return 0
        if left <= start and right >= end:
            return self.tree[node]
        
        mid, left_node, right_node = self.get_indices(node, start, end)
        if right <= mid:
            return self.query_max(left_node, start, mid, left, right)
        elif left > mid:
            return self.query_max(right_node, mid + 1, end, left, right)
        else:
            left_max = self.query_max(left_node, start, mid, left, mid)
            right_max = self.query_max(right_node, mid + 1, end, mid + 1, right)
            return max(left_max, right_max)

    def update(self, node, start, end, index, value):
        if start == end:
            self.tree[node] = value
        else:
            mid, left_node, right_node = self.get_indices(node, start, end)
            if index <= mid:
                self.update(left_node, start, mid, index, value)
            else:
                self.update(right_node, mid + 1, end, index, value)
            self.tree[node] = max(self.tree[left_node], self.tree[right_node])


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        max_num = max(nums)
        seg_tree = SegmentTree(max_num + 1)
        ans = 0
        for num in nums:
            prev_max_len = seg_tree.query_max(0, 0, max_num, max(0, num - k), num - 1)
            curr_max_len = prev_max_len + 1
            ans = max(ans, curr_max_len)
            # trictly increasing, 
            # the difference between adjacent elements in the subsequence is at most k.
            seg_tree.update(0, 0, max_num, num, curr_max_len)
        return ans
29600