1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| struct Seg{ int mi, ma, v; Seg* left, *right; Seg(vector<int>& A, int l, int r): mi(A[l]), ma(A[r]), v(0), left(nullptr), right(nullptr) { if(l != r) { int m = l + (r - l) / 2; left = new Seg(A,l,m); right = new Seg(A,m+1,r); } } void update(int n, int k) { if(mi <= n and n <= ma) { v = max(v, k); if(left) left->update(n,k); if(right) right->update(n,k); } } int query(int n) { if(ma < n) return v; if(mi >= n) return 0; return max(left ? left->query(n) : 0, right ? right->query(n) : 0); } };
int Solution::solve(vector<vector<int> > &A) { vector<int> S; for(auto vec : A) S.push_back(vec[1]); sort(begin(S), end(S)); S.erase(unique(begin(S), end(S)), end(S)); Seg* seg = new Seg(S,0,S.size() - 1); int res = 0; for(auto vec : A) { auto a = vec[0], b = vec[1]; int now = seg->query(a); res = max(res, now + 1); seg->update(b, now + 1); } return res; }
|