message: Update longest-increasing-subsequence.cpp
diff: @@ -65,10 +65,106 @@ private:
  }
  };
  +// Time: O(nlogn)
  +// Space: O(n)
  +// optimized from Solution4
  +class Solution3 {
  +public:
  + int lengthOfLIS(vector<int>& nums) {
  + set<int> sorted_nums(cbegin(nums), cend(nums));
  + unordered_map<int, int> lookup;
  + for (const auto& num : sorted_nums) {
  + lookup[num] = size(lookup);
  + }
  + SegmentTree segment_tree(size(lookup));
  + for (const auto& num : nums) {
  + segment_tree.update(lookup[num], lookup[num],
  + (lookup[num] >= 1) ? segment_tree.query(0, lookup[num] - 1) + 1 : 1);
  + }
  + return (size(lookup) >= 1) ? segment_tree.query(0, size(lookup) - 1) : 0;
  + }
  +
  +private:
  + class SegmentTree {
  + public:
  + SegmentTree(int N)
  + : N_(N),
  + tree_(2 * N),
  + lazy_(N)
  + {
  + H_ = 1;
  + while ((1 << H_) < N) {
  + ++H_;
  + }
  + }
  +
  + void update(int L, int R, int h) {
  + L += N_; R += N_;
  + int L0 = L, R0 = R;
  + while (L <= R) {
  + if ((L & 1) == 1) {
  + apply(L++, h);
  + }
  + if ((R & 1) == 0) {
  + apply(R--, h);
  + }
  + L >>= 1; R >>= 1;
  + }
  + pull(L0); pull(R0);
  + }
  +
  + int query(int L, int R) {
  + L += N_; R += N_;
  + auto result = 0;
  + push(L); push(R);
  + while (L <= R) {
  + if ((L & 1) == 1) {
  + result = max(result, tree_[L++]);
  + }
  + if ((R & 1) == 0) {
  + result = max(result, tree_[R--]);
  + }
  + L >>= 1; R >>= 1;
  + }
  + return result;
  + }
  +
  + private:
  + int N_, H_;
  + vector<int> tree_, lazy_;
  +
  + void apply(int x, int val) {
  + tree_[x] = max(tree_[x], val);
  + if (x < N_) {
  + lazy_[x] = max(lazy_[x], val);
  + }
  + }
  +
  + void pull(int x) {
  + while (x > 1) {
  + x >>= 1;
  + tree_[x] = max(tree_[x * 2], tree_[x * 2 + 1]);
  + tree_[x] = max(tree_[x], lazy_[x]);
  + }
  + }
  +
  + void push(int x) {
  + for (int h = H_; h > 0; --h) {
  + int y = x >> h;
  + if (lazy_[y] > 0) {
  + apply(y * 2, lazy_[y]);
  + apply(y * 2 + 1, lazy_[y]);
  + lazy_[y] = 0;
  + }
  + }
  + }
  + };
  +};
  +
  // Time: O(n^2)
  // Space: O(n)
  // Traditional DP solution.
  -class Solution3 {
  +class Solution4 {
  public:
  int lengthOfLIS(vector<int>& nums) {
  const int n = nums.size();
  