<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, n, fn):
        self.n = n
        self.fn = fn
        self.tree = [0] * (2 * n)
       
    def query(self, l, r):
        l += self.n
        r += self.n
        res = 0
        while l <= r: # => l == r になった値が反映されずにずれた
            if l & 1 == 1:
                res = self.fn(res, self.tree[l])
                l += 1
            # if r & 1 == 1: # => 個人的に分かりにくいと思う
            #     r -= 1
            #     res = self.fn(res, self.tree[r])
            if r & 1 == 0 :
                res = self.fn(res, self.tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res
    
    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i >>= 1
            self.tree[i] = self.fn(self.tree[i * 2], self.tree[i * 2 + 1])
            
class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        n = max(nums)
        res = 1
        tree = SegmentTree(n, max)
        for num in nums:
            current_index = num - 1 # => インデックスと値がずれているので補正する
            prev_num = num - 1
            prev_index = prev_num - 1
            
            mm = tree.query(max(0, current_index-k), prev_index) # => strict increasing なので prev_index を使う
            # print(num, current_index, mm, max(0, current_index-k), prev_index)
            tree.update(current_index, mm + 1)
            # print(num, current_index, mm, tree.tree)
            res = max(res, mm + 1)
        # print(res, tree.tree, len(tree.tree))
        return res
26300