<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 Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        # 线段树是一个平衡二叉树，最终所有叶子结点为单个元素，所以有n个叶子结点，平衡二叉树内部结点数量等于叶子结点-1，所以一共2n-1个
        # 定义线段树中p结点的左子树结点为2p，右子树为2p+1
        # 理论上能优化到2n，但因为成对叶子结点不一定是相邻的，所以只能假设最底层的叶子结点是满的
        # 这时候一共有math.ceil(log_2 n)+1层，最后一层有2**math.ceil(log_2 n)个元素，这个是小于2n的
        n = max(nums)
        segmentTree = [0 for _ in range(2**(math.ceil(math.log(n,2))+1))]
        res = -1
        def query(l,r,p = 1,cl = 1,cr = n):
            if cl == l and cr == r:
                return segmentTree[p]
            mid = (cl+cr)//2
            # l,r 落在左子树
            if mid >= r:
                return query(l,r,2*p,cl,mid)
            # l,r 落在右子树
            if mid < l:
                return query(l,r,2*p+1,mid+1,cr)
            left = query(l,mid,2*p,cl,mid)
            right = query(mid+1,r,2*p+1,mid+1,cr)
            return max(right,left)
        def update(idx,value,p = 1,cl = 1,cr = n):
            segmentTree[p] = max(segmentTree[p],value)
            if cl == cr:
                return
            mid = (cl+cr)//2
            # 要更新的值落在左子树
            if mid >= idx:
                update(idx,value,2*p,cl,mid)
            # 要更新的值落在右子树
            if mid < idx:
                update(idx,value,2*p+1,mid+1,cr)
        for num in nums:
            if num == 1:
                update(idx = num,value = 1)
                res = max(res,1)
            else:
                c = query(l = max(1,num-k),r = num-1)+1
                update(idx = num,value = c)
                res = max(c,res)
        return res

37600