<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 

class Node:
    def __init__(self, l, r):
        self.l = l 
        self.r = r 
        self.lis = 0 
        self.left_node = None 
        self.right_node = None 
    
    def update(self, val, new_max):
        l, r = self.l, self.r 
        if val < l or val > r:
            return 

        if l == r:
            self.lis = max(self.lis, new_max)
            return 
        
        self.lis = max(self.lis, new_max)
        mid = (l + r) // 2 
        if not self.left_node:
            self.left_node = Node(l, mid)
        if not self.right_node:
            self.right_node = Node(mid + 1, r)
        
        self.left_node.update(val, new_max)
        self.right_node.update(val, new_max)
    
    def query(self, ql, qr):
        l, r = self.l, self.r 
        if ql <= l and r <= qr:
            return self.lis 
        
        if qr < l or ql > r:
            return 0
        
        max_lis = 0 
        if self.left_node:
            max_lis = max(max_lis, self.left_node.query(ql, qr))
        if self.right_node:
            max_lis = max(max_lis, self.right_node.query(ql, qr))
        
        return max_lis


class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        node = Node(1, 10**5)
        result = 0
        for num in nums[::-1]:
            max_num = num + k 
            max_lis = node.query(num + 1, max_num) + 1
            result = max(result, max_lis)
            node.update(num, max_lis)
        
        return result 
56000