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):
class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res


def solve(n, k, a_list):
    seg_tree = SegmentTree([0] * 300001, seg_func=max, seg_func_null=0)
    for i in range(n):
        a = a_list[i]
        r = seg_tree.query(max(0, a - k), min(a + k + 1, 300001))
        seg_tree.update(a, r + 1)
    return seg_tree.query(0, 300001)


def main():
    n, k = map(int, input().split())
    a_list = [int(input()) for _ in range(n)]
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(10, 3, [1, 5, 4, 3, 8, 6, 9, 7, 2, 4]) == 7


if __name__ == "__main__":
    test()
    main()

Solution (Python):
class segtree():
    def segfunc(x,y):
        return min(x,y)
    
    ide_ele = -1
    n=1
    init_val=[0]*n
    
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
 
        
        for i in range(self.n):
            self.seg[i+self.num-1]=self.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+1:
            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

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
def solve1(A,K):
    INF=10**15
    MAX_A=300000
    G=segtree([0 for i in range(MAX_A+1)],max,-INF)
    dp=[0 for i in range(N)]
    dp[0]=1
    G.update(A[0],1)
    for i in range(1,N):
        
        inf=max(0,A[i]-K)
        sup=min(MAX_A+1,A[i]+K+1)
        dp[i]=G.query(inf,sup)+1
        G.update(A[i],dp[i])
    
    return max(dp)

def solve2(A,K):
    N=len(A)
    dp=[1 for i in range(N)]
    for i in range(1,N):
        for j in range(i):
            if abs(A[j]-A[i])<=K:
                dp[i]=max(dp[i],dp[j]+1)
    
    return max(dp)

print(solve1(A,K))

Solution (Python):
class SegTree:
    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 += 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):
        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 segfunc(x, y):
    return max(x, y)

def main():

    N, K = map(int, input().split())
    B = []
    for _ in range(N): B.append(int(input()))
    a = [0 for _ in range(max(B)+1)]
    ide_ele = 0
    seg = SegTree(a, segfunc, ide_ele)

    ans = 0
    for i in range(N):
        l = max(0, B[i]-K)
        r = min(len(a), B[i]+K)
        v = seg.query(l, r+1)
        ans = max(ans, max(1, v+1))
        seg.update(B[i], max(1, v+1))
        

    return ans

if __name__ == '__main__':
    print(main())

Solution (Python):









class SegmentTree:
    
    
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    
    
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    
    
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] 
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    
    
    
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

from sys import stdin
input = stdin.buffer.readline

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

    
    st = SegmentTree(n=300001, default=0)

    for _ in range(n):
        a = int(input())
        st.update(a, st.query(max(0, a - k), min(300001, a + k + 1)) + 1)

    print(st.data[1])

main()

Solution (Python):

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



ide_ele = -1


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())
Num_max = 3*10**5 + 1

A = [int(input()) for _ in range(N)]
st = SegTree([0 for _ in range(Num_max+4)], segfunc, ide_ele)


st.update(A[0], 0)  
for i in range(N):
  l = st.query(max(A[i] - K, 0), min(A[i] + K+1, Num_max))
  st.update(A[i], 1 + l)  
  


print(st.query(0, Num_max))

Solution (Python):

import sys
input = sys.stdin.readline
import bisect

class SegmentTree:
    def __init__(self, a):
        
        self.op = lambda a, b : max(a, b)
        
        self.e = 0 

        self.n = len(a)
        self.lv = (self.n - 1).bit_length()
        self.size = 2**self.lv
        self.data = [self.e] * (2*self.size - 1)
        
        self._check = lambda x, acc : acc >= x
        self._acc = self.e

        self.initialize(a)

    
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data[i] = self.op(self.data[i*2 + 1], self.data[i*2 + 2])

    
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self.op(self.data[2*k+1], self.data[2*k+2])

    
    def fold(self, l, r):
        L = l + self.size; R = r + self.size
        s = self.e
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.data[R-1])
            if L & 1:
                s = self.op(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n, k = map(int, input().split())
aa = []
aa_sorted = []
for i in range(n):
    a = int(input())
    aa_sorted.append((a, i))
    aa.append(a)

aa_sorted.sort()
aas = sorted(aa)

place_list = [-1] * n
for place, (val, index) in enumerate(aa_sorted):
    place_list[index] = place

len_list = [0] * n
ST = SegmentTree(len_list)

ans = 0
for i, a in enumerate(aa):
    l = bisect.bisect_left(aas, a - k)
    r = bisect.bisect_right(aas, a + k)
    max_score = ST.fold(l, r)
    ST.update(place_list[i], max_score + 1)
    ans = max(ans, max_score + 1)
print(ans)

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():
    vl = [0]*300001
    n,k = map(int, input().split())
    st = SegTree(vl,max,0)
    for _ in range(n):
        a = int(input())
        l = max(0,a-k)
        r = min(300001,a+k+1)
        curr_max = st.query(l,r)
        st.update(a,curr_max+1)

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

if __name__ == "__main__":
    main()

Solution (Python):
class SegTree:
    def __init__(self, op, e, n: int = -1, v: list = []):
        assert (len(v) > 0) | (n > 0)
        if(len(v) == 0):
            v = [e()] * n
        self.__n = len(v)
        self.__log = (self.__n - 1).bit_length()
        self.__size = 1 << self.__log
        self.__d = [e()] * (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 range(self.__size - 1, 0, -1):
            self.__update(i)

    def __update(self, k: int):
        self.__d[k] = self.__op(self.__d[2 * k], self.__d[2 * k + 1])

    def set(self, p: int, x):
        assert (0 <= p) & (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):
        assert (0 <= p) & (p < self.__n)
        return self.__d[p + self.__size]

    def prod(self, l: int, r: int):
        assert (0 <= l) & (l <= r) & (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 //= 2
            r //= 2

        return self.__op(sml, smr)

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

    def max_right(self, l: int, f):
        assert (0 <= l) & (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 //= 2
            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:
                break
        return self.__n

    def min_left(self, r: int, f):
        assert (0 <= r) & (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) & (r % 2):
                r //= 2
            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:
                break
        return 0


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k,*a = list(map(int,read().split()))

def op(x,y):
    x0,x1 = divmod(x,1<<20)
    y0,y1 = divmod(y,1<<20)
    if(x0 >= y0):
        return x
    else:
        return y

st = SegTree(op=max, e=lambda :0, v = list(range(300001)))
bef = [-1] * n
max_num = 0
last = -1
for i,ai in enumerate(a):
    l = max(0,ai-k)
    r = min(300000, ai+k)
    b0,b1 = divmod(st.prod(l,r+1),1<<20)
    if(b0 != 0):
        bef[i] = b1
    st.set(ai, ((b0+1)<<20) + i)
    if(max_num < b0+1):
        max_num = b0+1
        last = i

print(max_num)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	
	def calc(self, a, b):
		return max(a, b)

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

	
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

def main():
	N, K = getlist()
	n = 3 * (10 ** 5) + 2
	Seg = SegmentTree(n)
	for i in range(N):
		a = int(input())
		l = max(0, a - K)
		r = min(n - 1, a + K)
		res = Seg.query(l, r)
		Seg.update(a, res + 1)

	ans = Seg.query(0, n - 1)
	print(ans)




if __name__ == '__main__':
	main()

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]


import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
maxA = max(A)
st = SegmentTree(maxA+1, max, 0)

for i in range(N):
  mm = st.prod(max(0,A[i]-K),min(maxA,A[i]+K)+1)+1
  st.set(A[i],mm)
ans = st.all_prod()
print(ans)

Solution (Python):
def init_max(init_max_val):
    
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res


ide_ele_max = -1





N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
n = 1000000
lis = [0] * 1000000


num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max


init_max(lis)
dp = [0] * (N+1)
for i in range(N):
    val = query_max(max(0,A[i]-K),A[i]+K+1) +1
    dp[i] = val
    update_max(A[i],val)
print(max(dp))

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()

class SegmentTree:
 
    __slots__ = ["func", "e", "original_size", "n", "data"]
 
    def __init__(self, length_or_list, func=max, e=-10**18):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * (self.n*2)
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + \
                [self.e] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])
 
    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(
                self.data[2*index], self.data[2*index+1])
            index //= 2
 
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)
 
    def all_folded(self):
        return self.data[1]
 
    def __getitem__(self, index):
        return self.data[self.n + index]
 
    def max_right(self, l, f):
        
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            
            while l % 2 == 0:
                l //= 2
            if not f(self.func(left_folded, self.data[l])):
                while l < self.n:
                    l *= 2
                    if f(self.func(left_folded, self.data[l])):
                        left_folded = self.func(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.func(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size
 
    
    def min_left(self, r, f):
        
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            if not f(self.func(self.data[r], right_folded)):
                while r < self.n:
                    r = 2 * r + 1
                    if f(self.func(self.data[r], right_folded)):
                        right_folded = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n
            if r == r & -r:
                break
        return 0

def main():
    n, k= map(int, input().split())
    A = 300010    
    st = SegmentTree(A,e=0)
    for _ in range(n):
        q = int(input())
        update=st.folded(max(0,q-k), min(300005,q+k+1))
        st.replace(q,update+1)
    print(st.all_folded())



if __name__ == '__main__':
    main()

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())
st = SegTree([0] * 300001, segfunc, ide_ele)
for _ in range(n):
    a = int(input())
    v = st.query(max(0, a - k), min(300001, a + k + 1)) + 1
    st.update(a, v)
print(st.query(0, 300001))

Solution (Python):
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
A = [int(input()) for i in range(N)]

class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

segt = SegTree([0]*300001, lambda x,y:max(x,y), 0)
for a in A:
    l = max(0,a-K)
    r = min(300001,a+K+1)
    m = segt.query(l,r)
    segt.update(a,m+1)

print(segt.query(0,300001))

Solution (Python):
class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print()
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res
    
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]


def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a>b:
        return b
    else:
        return a


def main():
    N,K = list(map(int,input().split()))

    A = [int(input()) for i in range(N)]
    maxA = max(A)
    from collections import defaultdict

    ST1 = SegmentTree([0]*(maxA+1), smax, 0)

    D1 = [0]*N
    for i in range(N):
        a = A[i]
        b = ST1.get(smax(a-K,0),smin(a+K,maxA))
        c = ST1.get_one(a)
        d = smax(b+1,c)
        D1[i] = d
        ST1.substitute(a,d)

    ST2 = SegmentTree([0]*(maxA+1), smax, 0)

    D2 = [0]*N
    for i in range(N):
        a = A[N-i-1]
        b = ST2.get(smax(a-K,0),smin(a+K,maxA))
        c = ST2.get_one(a)
        d = smax(b+1,c)
        D2[N-i-1] = d
        ST2.substitute(a,d)

    D3 = [D1[i]+D2[i]-1 for i in range(N)]

    print(max(D3))

if __name__ == '__main__':
    main()