【題目敘述】https://atcoder.jp/contests/abl/tasks/abl_d
【解題想法】線段樹
#include <iostream>
using namespace std;
int n, k, st[300005<<2], ans;
void update(int x, int l, int r, int u, int d){
st[x] = max(st[x], d);
if (l == r) return;
int mid = (l+r)/2;
if (u <= mid) update(x<<1, l, mid, u, d);
else update(x<<1|1, mid+1, r, u, d);
}
int query(int x, int l, int r,int ql, int qr){
if (ql <= l && r <= qr) return st[x];
int mid = (l+r)/2;
int ret = 0;
if (ql <= mid) ret = max(ret, query(x<<1, l, mid, ql, qr));
if (mid < qr) ret = max(ret, query(x<<1|1, mid+1, r, ql, qr));
return ret;
}
int main() {
cin >> n >> k;
for (int i = 0, a, ret; i < n; i++){
cin >> a;
ret = query(1, 1, 300000, a-k, a+k);
ret++;
ans = max(ans, ret);
update(1, 1, 300000, a, ret);
}
cout << ans << "\n";
}