【題解】AtCoder ACL Beginner Contest D – Flat Subsequence

#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";
}