<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 TreeNode:
    def __init__(self, start, end, val, left, right):
        self.start = start
        self.end = end
        self.val = val
        self.left = left
        self.right = right

class SegmentTree:
    def __init__(self, n):
        self.root = self.build(0, n-1)
    def build(self, start, end):
        if start == end:
            return TreeNode(start, end, 0, None, None)

        mid = start + (end - start) // 2
        left = self.build(start, mid)
        right = self.build(mid+1, end)
        node = TreeNode(start, end, 0, left, right)
        return node

    def update(self, i, val):
        self.doUpdate(self.root, i, val)
    def doUpdate(self, node, i, val):
        if node.start == i and node.end == i:
            node.val = val
            return
        mid = node.start + (node.end - node.start) // 2
        if i <= mid:
            self.doUpdate(node.left, i, val)
        else:
            self.doUpdate(node.right, i, val)
        node.val = max(node.left.val, node.right.val)

    def query(self, start, end):
        if start > end:
            return 0
        return self.doQuery(self.root, start, end)
    def doQuery(self, node, start, end):
        if node.start == start and node.end == end:
            return node.val
        mid = node.start + (node.end - node.start) // 2
        if end <= mid:
            return self.doQuery(node.left, start, end)
        elif start > mid:
            return self.doQuery(node.right, start, end)
        return max(self.doQuery(node.left, start, mid), self.doQuery(node.right, mid+1, end))
    pass

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        N = len(nums)
        sortedNums = []
        for i in range(N):
            sortedNums.append([nums[i], i])
        sortedNums.sort()
        #lookup = [0 for _ in range(N)]
        #for newPos in range(N):
        #    num, oldPos = sortedNums[newPos]
        #    lookup[oldPos] = newPos

        tree = SegmentTree(N)

        def lower_bound(target):
            left, right = 0, N-1
            while left < right:
                mid = left + (right - left) // 2
                if sortedNums[mid][0] < target:
                    left = mid + 1
                else:
                    right = mid
            if sortedNums[left][0] < target:
                left += 1
            return left
    
        dp = [0 for _ in range(N)]
        dp[0] = 1
        tree.update(lower_bound(nums[0]), dp[0])

        res = 0
        res = max(res, dp[0])
        for i in range(1, N):
            target = nums[i] - k
            start = lower_bound(target)
            end = lower_bound(nums[i])
            dp[i] = tree.query(start, end-1) + 1
            res = max(res, dp[i])

            tree.update(end, dp[i])

        return res


68000