structSeg { int mi, ma, n; Seg *left, *right; Seg(vector<int>& A, int l, int r) : mi(A[l]), ma(A[r]), n(0), left(nullptr), right(nullptr) { if(l != r) { int m = l + (r - l) / 2; left = newSeg(A, l, m); right = newSeg(A, m + 1, r); } } voidupdate(int k, int v){ if(mi <= k and k <= ma) { n = max(n,v); if(left) left->update(k,v); if(right) right->update(k,v); } } intquery(int l, int r){ if(l <= mi and ma <= r) return n; if(r < mi or ma < l) return0; returnmax((left ? left->query(l,r) : 0), (right ? right->query(l,r) : 0)); } }; classSolution { public: intlengthOfLIS(vector<int>& A, int k){ int n = A.size(), res = 1; vector<int> S = A; sort(begin(S), end(S)); S.erase(unique(begin(S), end(S)), end(S)); Seg* seg = newSeg(S, 0, S.size() - 1); for(int i = n - 1; i >= 0; i--) { int now = 1 + seg->query(A[i] + 1, A[i] + k); res = max(res, now); seg->update(A[i], now); } return res; } };