class Node:
def __init__(self):
self.l = 0
self.r = 0
self.v = 0
class SegmentTree:
def __init__(self, n):
self.tr = [Node() for _ in range(4 * n)]
self.build(1, 1, n)
def build(self, u, l, r):
self.tr[u].l = l
self.tr[u].r = r
if l == r:
return
mid = (l + r) >> 1
self.build(u << 1, l, mid)
self.build(u << 1 | 1, mid + 1, r)
def modify(self, u, x, v):
if self.tr[u].l == x and self.tr[u].r == x:
self.tr[u].v = v
return
mid = (self.tr[u].l + self.tr[u].r) >> 1
if x <= mid:
self.modify(u << 1, x, v)
else:
self.modify(u << 1 | 1, x, v)
self.pushup(u)
def pushup(self, u):
self.tr[u].v = max(self.tr[u << 1].v, self.tr[u << 1 | 1].v)
def query(self, u, l, r):
if self.tr[u].l >= l and self.tr[u].r <= r:
return self.tr[u].v
mid = (self.tr[u].l + self.tr[u].r) >> 1
v = 0
if l <= mid:
v = self.query(u << 1, l, r)
if r > mid:
v = max(v, self.query(u << 1 | 1, l, r))
return v
class Solution:
def lengthOfLIS(self, nums: List[int], k: int) -> int:
tree = SegmentTree(max(nums))
res = 1
for v in nums:
t = tree.query(1, v - k, v - 1) + 1
res = max(res, t)
tree.modify(1, v, t)
return res