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):



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

N, K = map(int, input().split())
A = [int(input())+1 for _ in range(N)]
seg = SegTree([0 for i in range(300050)], segfunc, ide_ele)

answer = 0
for i in range(N):
    
    under = max(0,A[i]-K)
    upper = min(300050,A[i]+K)
    now = seg.query(under, upper+1)
    seg.update(A[i], now+1)
    
print(seg.query(0,300050))

Solution (Python):


import sys
input = sys.stdin.readline

class segmented_tree:
    X_unit = 0
    X_f = lambda self, a, b: max(a,b)
    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (2*N)
        
    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x 
        
        for i in range(self.N-1, 0, -1):
            self.X[i] = self.X_f(self.X[i<<1], self.X[i<<1|1])

    
    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i<<1],self.X[i<<1|1])
    
    
    def fold(self, l, r):
        l += self.N
        r += self.N
        vl = self.X_unit
        vr = self.X_unit
        
        while l < r:
            
            if l & 1:
                vl = self.X_f(vl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.X_f(vr, self.X[r])
            l >>= 1
            r >>= 1
        return self.X_f(vl,vr)

n,k = map(int, input().split())
As = [int(input()) for i in range(n)]

ans = 0
sg = segmented_tree(330000)

for a in As:
    l = max(0,a-k)
    r = min(300000,a+k)

    upd = sg.fold(l,r+1)
    ans = max(ans, upd+1)

    sg.set_val(a, upd+1)
print(ans)

Solution (Python):


import sys
input = sys.stdin.readline

class segmented_tree:
    X_unit = 0
    X_f = lambda self, a, b: max(a,b)
    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (2*N)
        
    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x 
        
        for i in range(self.N-1, 0, -1):
            self.X[i] = self.X_f(self.X[i<<1], self.X[i<<1|1])

    
    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i<<1],self.X[i<<1|1])
    
    
    def fold(self, l, r):
        l += self.N
        r += self.N
        vl = self.X_unit
        vr = self.X_unit
        
        while l < r:
            
            if l & 1:
                vl = self.X_f(vl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.X_f(vr, self.X[r])
            l >>= 1
            r >>= 1
        return self.X_f(vl,vr)

n,k = map(int, input().split())
As = [int(input()) for i in range(n)]
mx = 300001
ans = 0
sg = segmented_tree(330000)

for a in As:
    l = max(0,a-k)
    r = min(mx,a+k)

    upd = sg.fold(l,r+1)
    ans = max(ans, upd+1)

    sg.set_val(a, upd+1)
print(ans)

Solution (Python):



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

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
seg = SegTree([0 for i in range(300050)], segfunc, ide_ele)

answer = 0
for i in range(N):
    
    under = max(0,A[i]-K)
    upper = min(300050,A[i]+K)
    now = seg.query(under, upper+1)
    seg.update(A[i], now+1)
    
print(seg.query(0,300001))

Solution (Python):

import sys


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush


sys.setrecursionlimit(10 ** 7)
import math








INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

class segtree:
    '''init_val : i-indexed (init_val[0] = self.bin[1])'''
    def __init__(self, n, init = 0, init_val=None):
        self.n = n
        self.init = init
        self.k = math.ceil(math.log2(n))
        self.add_val = 1 << self.k

        self.bins = [self.init] * (1 << (self.k + 1))
        if init_val != None:
            self.update_set(init_val)
        self.caliculate()

    def __getitem__(self, idx):  
        return self.bins[idx + self.add_val]

    def update_set(self, vals):
        for idx, i in enumerate(range(self.add_val, self.add_val * 2)):
            if len(vals) > idx:
                self.bins[i] = vals[idx]
            else:continue

    def compare(self, l, r):
        return max(l ,r)

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val, by=True):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        if by:
            self.bins[k] += val
        else:
            self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        
        while True:
            
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        
        return ret

def run():
    N, K, *A = mapread()
    alim = max(A)
    st = segtree(alim+1, init = 0)

    for a in A:
        v = st.eval(max(0, a- K), min(alim, a + K))
        st.update(a, v + 1, by = False)

    print(st.bins[1])

if __name__ == "__main__":
    run()

Solution (Python):
import typing
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue



INF = 10 ** 16

MOD = 998244353


def ni(): return int(sys.stdin.readline())
def ns(): return map(int, sys.stdin.readline().split())
def na(): return list(map(int, sys.stdin.readline().split()))







def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    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])


def main():
    n, k = ns()
    a = [ni() for _ in range(n)]

    dp = [0 for _ in range(3*10**5+1)]

    st = SegTree(max, -1, dp)

    for ai in a:
        cnt = st.prod(max(0, ai-k), min(ai+k+1, 3*10**5+1))
        st.set(ai, cnt+1)
    ans = st.all_prod()
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, math
import io, os

from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write('\n'.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal


mod = 998244353
INF=float('inf')


def construct_sum(segtree,a,n,func=max):
    for i in range(n):
        segtree[n + i] = a[i]
    for i in range(n - 1, 0, -1):
        segtree[i] = func(segtree[2 * i], segtree[2 * i + 1])

def update(pos, x, func=max):
    pos += n-1
    segtree[pos] = x
    while (pos>1):
        pos>>=1
        segtree[pos] = func(segtree[2 * pos], segtree[2 * pos + 1])

def get(l, r, func=max):
    l += n-1
    r += n-1
    s = 0
    while (l <= r):
        if l & 1:
            s = func(segtree[l],s)
            l+=1
        if (r+1) & 1:
            s = func(segtree[r],s)
            r-=1
        l >>= 1
        r >>= 1
    return s

n,k=mdata()
a=[int(data()) for i in range(n)]
n=max(a)+1
segtree = [0]*(2*n)
construct_sum(segtree,[0]*n,n)
ans=0
for i in a:
    a1=get(max(i-k+1,1),min(i+k+1,n))+1
    update(i+1,a1)
    ans=max(ans,a1)
out(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n,k = map(int, input().split())
As = [int(input()) for i in range(n)]



INF = 0

mx = 300001
LV = (mx-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)


def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])


def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    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

ans = 0
update(As[0],As[0]+1,1)
for i, a in enumerate(As[1:]):
    l = max(0,a-k)
    r = min(mx,a+k)
    upd = query(l,r+1)
    if upd == -1:continue
    
    update(a, a+1, upd+1)
    ans = max(ans, upd+1)
print(ans)

Solution (Python):
class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.dp = [0 for _ in range(2 * n)]
        
    def update(self, k, a):
        k += self.n
        self.dp[k] = a
        while (k > 1):
            self.dp[k >> 1] = max(self.dp[k], self.dp[k ^ 1])
            k >>= 1
        
    def query(self, l, r):
        res = 0
        l, r = l + self.n, r + self.n
        while l < r:
            if l & 1:
                res = max(res, self.dp[l])
                l += 1
            if r & 1:
                res = max(res, self.dp[r - 1])
            l, r = l >> 1, r >> 1
        return res
    
    
n, k = map(int, input().split())
A = []
for _ in range(n):
    a = int(input())
    A.append(a)
num = max(A) + k + 1

st = SegmentTree(num)
for i in range(n):
    x = A[i]
    l = max(x - k, 0)
    r = min(x + k + 1, num)
    now = st.query(l, r) + 1
    st.update(x, now)
print(max(st.dp))

Solution (Python):
def main():
    n,k = map(int,input().split())
    a = []
    for _ in range(n):
        a.append(int(input()))
    DP = [[] for _ in range(n)]
    DP[1].append(0)
    M = 1
    for i in range(1,n):
        m = M
        flg = 0
        while m>0:
            for p in DP[m]:
                if abs(a[i]-a[p])<=k:
                    DP[m+1].append(i)
                    flg = 1
                    if m+1>M:
                        M=m+1
                    break
            if flg==1:
                break
            m -= 1
        if flg==0:
            DP[1].append(i)
    print(M)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

n,k = map(int, input().split())
As = [int(input()) for i in range(n)]



INF = 0

mx = 300001
LV = (mx-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)


def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])


def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    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

update(As[0],As[0]+1,1)
for i, a in enumerate(As[1:]):
    l = max(0,a-k)
    r = min(mx,a+k)
    upd = query(l,r+1)
    if upd == -1:continue
    
    update(a, a+1, upd+1)

ans = 0
for a in set(As):
    ans = max(ans,query(a,a+1))
print(ans)

Solution (Python):

class SegmentTree():
  def __init__(self, n, oper, e):
    self.n = n
    self.oper = oper
    self.e = e
    self.log = (n - 1).bit_length()
    self.size = 1 << self.log
    self.data = [e] * (2 * self.size)

  def update(self, k):
    self.data[k] = self.oper(self.data[2 * k], self.data[2 * k + 1])

  def build(self, arr):
    
    for i in range(self.n):
      self.data[self.size + i] = arr[i]
    for i in range(self.size-1,0,-1):
      self.update(i)

  def set(self, p, x):
    
    p += self.size
    self.data[p] = x
    for i in range(1, self.log + 1):
      self.update(p >> i)

  def get(self, p):
    
    return self.data[p + self.size]

  def prod(self, l, r):
    
    sml = smr = self.e
    l += self.size
    r += self.size
    while l < r:
      if l & 1:
        sml = self.oper(sml, self.data[l])
        l += 1
      if r & 1:
        r -= 1
        smr = self.oper(self.data[r], smr)
      l >>= 1
      r >>= 1
    return self.oper(sml, smr)

  def all_prod(self):
    return self.data[1]

  def max_right(self, l, f):
    
    
    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.oper(sm, self.data[l])):
        while l < self.size:
          l = 2 * l
          if f(self.oper(sm, self.data[l])):
            sm = self.oper(sm, self.data[l])
            l += 1
        return l - self.size
      sm = self.oper(sm, self.data[l])
      l += 1
      if (l & -l) == l: break
    return self.n

  def min_left(self, r, f):
    
    
    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.oper(self.data[r], sm)):
        while r < self.size:
          r = 2 * r + 1
          if f(self.oper(self.data[r], sm)):
            sm = self.oper(self.data[r], sm)
            r -= 1
        return r + 1 - self.size
      sm = self.oper(self.data[r], sm)
      if (r & -r) == r: break
    return 0




n,k=map(int,input().split())
a=[0]*n
for i in range(n):
    a[i]=int(input())
maxa=max(a)

st = SegmentTree(maxa+1,max,0)



ans=0
for i in range(n):
    l=max(a[i]-k,0)
    r=min(a[i]+k,300000)
    tmp=st.prod(l,r+1)+1

    ans=max(ans,tmp)
    st.set(a[i],tmp)

print(ans)

Solution (Python):
import typing

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1
    return x

class SegTree:
    '''
    op: 結合律が成り立つ演算
    e: 単位元 A op e = A and e op A = A が成り立つe
    足し算の場合 0, 掛け算の場合 1
    '''
    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:
        """
        d[p]にxを代入
        d[p]が変更された分を他の部分に反映する
        O(logn)
        """
        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:
        """
        d[p]を返す
        O(1)
        """
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left: int, right: int) -> typing.Any:
        """
        op(d[left],・・・,d[right-1])を返す
        O(logn)
        """
        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:
        """
        op(d[0],・・・,d[n-1])を返す
        O(1)
        """
        return self._d[1]
    
    def max_right(self,
                left: int,
                f: typing.Callable[[typing.Any], bool]
                ) -> int:
        """
        fが単調とすれば、f(op(d[left],・・・,d[right-1])) = true
        となる最大のrightを求められる
        O(logn)
        """
        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:
        """
        fが単調とすれば、f(op(d[left],・・・,d[right-1])) = true
        となる最小のleftを求められる
        O(logn)
        """

        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])



def main():
    N: int
    K: int
    A: list
    MAX_A: int = 300005
    N, K = map(int, input().split())
    A = list(int(input()) for _ in range(N))
    seg = SegTree(max,0,MAX_A)
    for i in range(N):
        x: int = A[i]
        left = max(0, A[i] - K)
        right = min(MAX_A, A[i] + K + 1)
        now = seg.prod(left, right) + 1
        seg.set(x, max(now, seg.get(x)))

    print(seg.all_prod())

if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline


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= [int(input()) for i in range(n)]


v = [-float('inf')]*(pow(10,5)*3+1)
seg = SegTree(v, segfunc, ide_ele)


for i in a:
    r=min(i+k+1,3*pow(10,5)+1)
    l=max(i-k,0)
    if seg.query(l, r)==-float('inf'):
        seg.update(i, 1)
    else:
        x=seg.query(l, r)
        seg.update(i,x+1)

print(seg.query(0,pow(10,5)*3+1))

Solution (Python):
n,k=map(int,input().split())

class SegmentTree:
    def __init__(self,n,ele):

        self.ide_ele = ele

        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num


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

    def init(self,init_val):
        
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

st=SegmentTree(300001,0)
dp=[0]*n
for i in range(n):
    a=int(input())
    dp[i]=max(dp[i],st.query(max(0,a-k),min(300000,a+k)+1)+1)
    st.update(a,dp[i])
    dp[i]=max(dp[i],st.query(0,300001))
print(dp[n-1])