Untitled

class SegTree {
public:
    // [0, n)
    explicit SegTree(size_t n): root(make_unique<Node>(0, n)) {
    }

    void set(size_t idx, int v) {
        root->set(idx, v);
    }

    int get(size_t l, size_t r) const {
        return root->get(l, r);
    }

private:
    struct Node;
    struct Node {
        unique_ptr<Node> lnode;
        unique_ptr<Node> rnode;
        
        size_t l;
        size_t r;
        int val;

        // [l, r)
        Node(size_t l, size_t r): l(l), r(r) {
        }

        size_t mid() const {
            return (l + r) >> 1;
        }

        bool isRange() const {
            return r - l > 1;
        }

        void set(size_t idx, int v) {
            if (!isRange()) {
                val = max(val, v);
                return;
            }

            if (idx < mid()) {
                if (!lnode) {
                    lnode = make_unique<Node>(l, mid());
                }
                lnode->set(idx, v);
            } else {
                if (!rnode) {
                    rnode = make_unique<Node>(mid(), r);
                }
                rnode->set(idx, v);
            }

            int lv = lnode ? lnode->val : 0;
            int rv = rnode ? rnode->val : 0;
            val = max(lv, rv);
        }

        int get(size_t l, size_t r) const {
            if (this->l == l && this->r == r) {
                return val;
            }

            if (r < mid()) {
                return lnode ? lnode->get(l, r) : 0;
            } else if (l >= mid()) {
                return rnode ? rnode->get(l, r) : 0;
            }

            int lv = lnode ? lnode->get(l, mid()) : 0;
            int rv = rnode ? rnode->get(mid(), r) : 0;
            return max(lv, rv);
        }
    };

    unique_ptr<Node> root;
};

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& xs) {
        size_t n = xs.size();
        vector<int> dp(n, 1);
        SegTree tree(1e7 + 10);
        for (size_t i = 0; i < n; ++i) {
            dp[i] = tree.get(0, xs[i] + 1) + 1;
            tree.set(xs[i], dp[i]);
        }
        return dp;
    }
};