Problem:
 Score : 400 points    Problem Statement You are given a sequence A_1, A_2, ..., A_N and an integer K .  Print the maximum possible length of a sequence B that satisfies the following conditions:   B is a (not necessarily continuous) subsequence of A .  For each pair of adjacents elements of B , the absolute difference of the elements is at most K .       Constraints  1 \leq N \leq 300,000  0 \leq A_i \leq 300,000  0 \leq K \leq 300,000  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K  A_1  A_2  :  A_N       Output Print the answer.        Sample Input 1 10 3
1
5
4
3
8
6
9
7
2
4      Sample Output 1 7  For example, B = (1, 4, 3, 6, 9, 7, 4) satisfies the conditions.   It is a subsequence of A = (1, 5, 4, 3, 8, 6, 9, 7, 2, 4) .  All of the absolute differences between two adjacent elements ( |1-4|, |4-3|, |3-6|, |6-9|, |9-7|, |7-4| ) are at most K = 3 .

Solution (Python):
import sys



import typing
 
def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1
 
    return x
 
 
def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2
 
    return x
 
class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
 
        if isinstance(v, int):
            v = [e] * v
 
        self._n = len(v)
        
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
 
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)
 
    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n
 
        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)
 
    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n
 
        return self._d[p + self._size]
 
    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size
 
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1
 
        return self._op(sml, smr)
 
    def all_prod(self) -> typing.Any:
        return self._d[1]
 
    def max_right(self, left: int,
                  f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)
 
        if left == self._n:
            return self._n
 
        left += self._size
        sm = self._e
 
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not f(self._op(sm, self._d[left])):
                while left < self._size:
                    left *= 2
                    if f(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1
 
        return self._n
 
    def min_left(self, right: int,
                 f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= right <= self._n
        assert f(self._e)
 
        if right == 0:
            return 0
 
        right += self._size
        sm = self._e
 
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not f(self._op(self._d[right], sm)):
                while right < self._size:
                    right = 2 * right + 1
                    if f(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)
 
        return 0
 
    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
 


input = sys.stdin.readline
 
N, K = map(int, input().split())
A = []
for _ in range(N):
    A.append(int(input()))

MAX_A = 3*10**5+5

dp = [0 for _ in range(MAX_A)]
segtree = SegTree(max, 0, [0] * MAX_A)
for i in range(N):
    x = A[i]
    l = max(0, x-K)
    r = min(MAX_A, x+K+1)
    now = segtree.prod(l, r) + 1
    segtree.set(x, now)
 
print(segtree.prod(0, MAX_A))

Solution (Python):
from collections import deque
INFTY = 10**10
def update(i,a):
    j = i+N
    T[j] = a
    j = j//2
    while j>=1:
        T[j]=max(T[2*j],T[2*j+1])
        j = j//2
def find(l,r):
    que = deque([(1,0,N)])
    A = []
    while que:
        j,x,D = que.popleft()
        y = x+D
        if y<=l or x>=r:
            A.append(-INFTY)
        elif l<=x and y<=r:
            A.append(T[j])
        else:
            que.append((2*j,x,D//2))
            que.append((2*j+1,x+D//2,D//2))
    return max(A)
n,K = map(int,input().split())
A = [int(input()) for _ in range(n)]
k = 0
while 2**k<3*10**5:
    k += 1
N = 2**k
T = [-INFTY for _ in range(2*N)]
dp = [0 for _ in range(n)]
dp[0]=1
update(A[0],dp[0])
for i in range(1,n):
    a = A[i]
    l = max(0,a-K)
    r = min(a+K,N-1)+1
    dp[i] = max(1,find(l,r)+1)
    update(a,dp[i])
dmax = 0
for i in range(n):
    dmax = max(dmax,dp[i])
print(dmax)

Solution (Python):
n,k=map(int,input().split())
a=[]
for i in range(n):
    a.append(int(input()))
dp=[0]*(300010)


def segfunc(x, y):
    return max(x,y)



ide_ele =0


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

seg=SegTree(dp,segfunc,0)
for i in a:
    l=max(i-k,0)
    r=min(i+k,300005)

    dp[i]=seg.query(l,r+1)+1
    seg.update(i,dp[i])
print(max(dp))

Solution (Python):

def segfunc(x, y):
    return max(x, y)



ide_ele = float('-inf')


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N, K = map(int,input().split())
a = [0] * 300001
seg = SegTree(a, segfunc, ide_ele)
ans = 0
for _ in range(N):
    A = int(input())
    x = seg.query(max(0, A - K), min(300001, A + K + 1))
    seg.update(A, x + 1)
    ans = max(ans, x + 1)
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

from typing import Callable, TypeVar, List

T = TypeVar('T')
class SegTree:
    def __init__(self, v: List[T], op: Callable[[T, T], T], e: Callable[[], T]) -> None:
        self._n = len(v)
        self.log = (self._n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e() for _ in range(2 * self.size)]
        self.op = op
        self.e = e
        for i in range(self._n):
            self.d[self.size + i] = v[i]
        for i in reversed(range(1, self.size)):
            self.__update__(i)

    @classmethod
    def init_e(cls, n: int, op: Callable[[T, T], T], e: Callable[[], T]) -> 'SegTree':
        return cls([e() for _ in range(n)], op, e)

    
    def set(self, p: int, x: T) -> None:
        assert 0 <= p < self._n
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.__update__(p >> i)

    def get(self, p: int) -> T:
        assert 0 <= p < self._n
        return self.d[p + self.size]

    
    def prod(self, l: int, r: int) -> T:
        assert 0 <= l <= self._n and 0 <= r <= self._n
        sml = self.e()
        smr = self.e()
        l += self.size
        r += self.size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self) -> T:
        return self.d[1]

    
    def max_right(self, l: int, f: Callable[[T], bool]):
        assert 0 <= l <= self._n
        assert f(self.e())
        if l == self._n:
            return self._n
        l += self.size
        sm = self.e()
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l *= 2
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l:
                return self._n

    def min_left(self, r: int, f: Callable[[T], bool]):
        assert 0 <= r <= self._n
        assert f(self.e())
        if r == 0:
            return 0
        r += self.size
        sm = self.e()
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r:
                return 0

    def __update__(self, k: int) -> None:
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])










n,k = inpl()
a = [inp() for _ in range(n)]
dp = SegTree([0]*300010, max, lambda:-1)
for i,x in enumerate(a):
    l = max(0,x-k)
    r = min(300002,x+k+1)
    now = dp.prod(l,r)
    dp.set(x, now+1)
print(dp.all_prod())

Solution (Python):

class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)


'''
memo:
GCD... INFをide_eleに設定して、片方がINFの場合はもう片方を返す
def gcd2(a,b):
    if a >= INF: return b
    elif b >= INF: return a
    else return gcd(a,b)


vl = [1,4,6,8,9]

def add(a,b): return a+b
st = SegTree(vl,add,0)
st = SegTree(vl,(lambda a,b: a+b),0)
st = SegTree(vl,min,10**10)

print(st.query(2,4))
st.update(4,-4)
print(st.query(2,5))
st.update(0,-10)
print(st.query(0,5))
'''

def main():
    n,k = map(int, input().split())
    seg = SegTree([0]*300001, max, 0)
    for _ in range(n):
        a = int(input())
        l = max(a-k,0)
        r = min(a+k,300000)
        c_max = seg.query(l,r+1)
        seg.update(a,c_max+1)

    ans = seg.query(0,300001)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

class SegTree():
    """
    0-indexedの配列[a0, a1, a2, ..., a(N-1)]に対して以下のクエリをそれぞれO(logx)で行う：
        1. i番目の要素にxを代入
        2. 半開区間[i, j)内の最小値を返す
    self.id_elemとself.funcを変えることでRmQ以外にも例えばRMQに対応可能。
    参考：https://juppy.hatenablog.com/entry/2019/05/02/蟻本_python_セグメント木_競技プログラミング_Atcoder
    """
    def __init__(self, N):
        
        self.id_elem = 0
        self.func = max

        
        self.num_max = 2 ** ((N - 1).bit_length())
        self.x = [self.id_elem] * (2 * self.num_max - 1)

    def get_elem(self, i):
        """
        i番目の要素を返す
        """
        return self.x[self.num_max + i - 1]

    def update(self, i, x):
        """
        i番目の要素にxを代入
        """
        i += self.num_max - 1
        self.x[i] = x
        while (i > 0):
            i = (i - 1) // 2
            self.x[i] = self.func(self.x[i * 2 + 1], self.x[i * 2 + 2])

    def query(self, i=0, j=-1):
        """
        半開区間[i, j)内の最小値を返す
        query()で配列全体に対してクエリを実行する
        """
        if j == -1: j = self.num_max
        i += self.num_max - 1
        j += self.num_max - 1
        res = self.id_elem
        
        while i < j:
            if i % 2 == 0:
                res = self.func(res, self.x[i])
                i += 1
            if j % 2 == 0:
                res = self.func(res, self.x[j - 1])
            i = (i - 1) // 2
            j = (j - 1) // 2
        return res

def main():
    N, K = map(int, input().split())
    """
    愚直に解けそうに無いのでdpを考える：dp[i][j] = (0~i番目まで見た時に最後の数がjで終わる部分列の最大長)
    このdpはO(N^2)なのでそのままでは実行不可能だが、ひとまず遷移を考えてみると
        dp[i][j] = max(dp[i-1][j-K], dp[i-1][j-K+1], ..., dp[i-1][j+K]) + 1
    ここのmaxをセグ木で導出すれば計算量はO(NlogN)で間に合う。
    """
    dp = SegTree(300001)
    for _ in range(N):
        a = int(input())
        
        now = dp.query(max(0, a - K), min(300001, a + K + 1))
        dp.update(a, now + 1)
    print(dp.query())


if __name__ == "__main__":
    main()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
from collections import deque, defaultdict, Counter
import heapq


def segfunc(x, y):
    return max(x, y)





ide_ele = - float('inf')



class SegTree:
    """
    init(init_val, segfunc, ide_ele): 配列init_valで初期化、構築
    update(k, x): k番目の値をxに更新
    query(l, r): 区間[l, r)をsegfuncしたものを返す
    """

    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        :param k: index(0-index)
        :param x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        :param l: 0-index
        :param r: 0-index
        :return:
        """
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
def main():
    N, K = MI()
    A = [0] * (6 * 10 ** 5 + 1)
    seg = SegTree(A, segfunc, ide_ele)
    for i in range(N):
        a = I()
        b = seg.query(max(0, a - K), a + K + 1)
        seg.update(a, b + 1)
    print(seg.query(1, 3 * 10 ** 5 + 1))
if __name__ == "__main__":
    main()

Solution (Python):
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 

import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

class SegTree():
    def __init__(self, n_val, init_ele, combiner):
        self.n_val = n_val
        self.n = 1 << (self.n_val - 1).bit_length()
        self.tree = [init_ele] * (2 * self.n)
        self.combiner = combiner
        self.init_ele = init_ele

    def init_tree(self, data):
        self.data = data
        for x in range(self.n):
            self.tree[x + n] = self.data[x]
        for x in range(self.n - 1, 0, -1):
            self.tree[x] = self.combiner(self.tree[x<<1], self.tree[(x<<1) + 1])

    def query(self, l, r):
        l = l + self.n
        r = r + self.n
        res = self.init_ele
        while l < r:
            if l & 1:
                res = self.combiner(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.combiner(res, self.tree[r])
            l = l >> 1
            r = r >> 1
        return res

    def update_single(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx > 0:
            self.tree[idx>>1] = self.combiner(self.tree[idx], self.tree[idx ^ 1])
            idx >>= 1


def solve():
    
    n, k = map(int, input().split())

    n_val = 3 * (10 ** 5)

    arr = [int(input()) for _ in range(n)]
    s_tree = SegTree(n_val, 0, max)

    for a in arr:
        s_tree.update_single(a, s_tree.query(max(a - k, 0), min(a + k, n_val) + 1) + 1)
    cout<<s_tree.query(1, n_val + 1)<<endl






def main():
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
def segfunc(x, y): return max(x, y)

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300000)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300000))

Solution (Python):
def segfunc(x, y): return max(x, y)

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300005))

Solution (Python):
class SegmentTree:
    def __init__(self, n, segment_func, identity_element):
        self.n = n
        self.num = 1 << (self.n - 1).bit_length()
        self.segment_func = segment_func
        self.identity_element = identity_element
        self.segment_tree = [self.identity_element] * (2 * self.num)

    def initialize(self, val_arr):
        for i in range(self.n):
            self.segment_tree[self.num + i] = val_arr[i]
        for i in range(self.num - 1, 0, -1):
            self.segment_tree[i] = self.segment_func(self.segment_tree[2 * i], self.segment_tree[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.segment_tree[idx] = val
        while idx > 1:
            self.segment_tree[idx >> 1] = self.segment_func(self.segment_tree[idx], self.segment_tree[idx ^ 1])
            idx >>= 1

    def query(self, left, right):
        res = self.identity_element
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segment_func(res, self.segment_tree[left])
                left += 1
            if right & 1:
                res = self.segment_func(res, self.segment_tree[right - 1])
            left >>= 1
            right >>= 1
        return res

    def bisect_left(self, left, right, target):
        left += self.num
        right += self.num
        left_min = -1
        right_min = -1
        while left < right:
            if left & 1:
                if self.segment_tree[left] >= target and left_min == -1:
                    left_min = left
                left += 1
            if right & 1:
                if self.segment_tree[right - 1] >= target:
                    right_min = right - 1
            left >>= 1
            right >>= 1
        if left_min != -1 or right_min != -1:
            res = left_min if left_min != -1 else right_min
            while res < self.num:
                if self.segment_tree[2 * res] >= target:
                    res *= 2
                else:
                    res *= 2
                    res += 1
            return res - self.num
        else:
            return self.n


def main():
    n, k = map(int, input().split())
    a = [int(input()) for _ in range(n)]
    max_val = 3 * 10 ** 5
    st = SegmentTree(max_val + 1, max, 0)
    for aa in a:
        st.update(aa, st.query(max(0, aa - k), min(max_val, aa + k) + 1) + 1)
    print(st.query(1, max_val + 1))


if __name__ == '__main__':
    main()

Solution (Python):
N, K, *A = map(int, open(0).read().split())

A = [a + 1 for a in A]
M = max(A)

N0 = 2 ** (M - 1).bit_length()
data = [0] * (2 * N0)

def update(k, x):
    k += N0 - 1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(l, r):
    L = l + N0; R = r + N0
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for a in A:
    x = query(max(1, a - K), min(a + K + 1, M + 1))
    update(a, x + 1)

print(query(1, M))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

class SegTree:
    def __init__(self, N, ele):
        self.num = 2**(N-1).bit_length()
        self.el = ele
        self.data = [ele]*(2*self.num)

    def calc(self, x, y):
        return max(x, y)

    def update(self, idx, x):
        idx += (self.num - 1)
        self.data[idx] = x
        while idx > 0:
            idx = (idx-1)//2
            self.data[idx] = self.calc(self.data[2*idx+1], self.data[2*idx+2])

    def query(self, l, r):
        L = l + self.num
        R = r + self.num
        res = self.el
        while L < R:
            if L & 1:
                res  = self.calc(res, self.data[L-1])
                L += 1
            if R & 1:
                R -= 1
                res = self.calc(res, self.data[R-1])
            L >>= 1
            R >>= 1
        return res
    
    def get(self, idx):
        idx += (self.num - 1)
        return self.data[idx]

n, k = map(int, input().split())
A = [int(input()) for _ in range(n)]
seg = SegTree(330000, 0)
max_a = 300010
for a in A:
    l = max(0, a-k)
    r = min(max_a, a+k+1)
    now = seg.query(l, r)
    seg.update(a, now+1)

print(seg.query(0, max_a))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

class SegTree:
    def __init__(self, N, ele):
        self.num = 2**(N-1).bit_length()
        self.el = ele
        self.data = [ele]*(2*self.num)

    def calc(self, x, y):
        return max(x, y)

    def update(self, idx, x):
        idx += (self.num - 1)
        self.data[idx] = x
        while idx > 0:
            idx = (idx-1)//2
            self.data[idx] = self.calc(self.data[2*idx+1], self.data[2*idx+2])

    def query(self, l, r):
        L = l + self.num
        R = r + self.num
        res = self.el
        while L < R:
            if L & 1:
                res  = self.calc(res, self.data[L-1])
                L += 1
            if R & 1:
                R -= 1
                res = self.calc(res, self.data[R-1])
            L >>= 1
            R >>= 1
        return res
    
    def get(self, idx):
        idx += (self.num - 1)
        return self.data[idx]

n, k = map(int, input().split())
A = [int(input()) for _ in range(n)]
seg = SegTree(330000, 0)
max_a = 300010
for a in A:
    l = max(0, a-k)
    r = min(max_a, a+k+1)
    now = seg.query(l, r)
    seg.update(a, now+1)

print(seg.query(0, max_a))