最长递增子序列

• 问一个长度为$n$的数组$a[i]$的最长上升子序列长度
• 这个问题非常简单了，朴素方法$O(n^2)$的转移即可，可以二分优化到$O(nlogn)$

变形

https://leetcode.cn/problems/longest-increasing-subsequence-ii/

• 现在加一个限制条件，要求相邻元素差值不能超过$k$，怎么办？我们也能很简单的写出$O(n^2)$的状态转移即设$dp[i]$表示前$i$个数的最长递增子序列，有$$dp[i]=(\underset{j<i,a[j]<a[i],a[i]-a[j]\le k}{\max }dp[j])+1$$，但是这里$a[i]$和$n$的范围都是$[1,10^5]$，所以寻找前缀最大值的时候需要$O(logn)$的时间复杂度，考虑使用线段树维护前缀值域，每次找最大的一个，然后更新当前值，因为同一个值新的必然比旧的更优

class Solution{
  int mx;
  // 线段树维护[l, r]满足条件的最大子序列长度
  vector<int> segtree;
public:
  int query(int o, int l, int r, int ql, int qr){
    if(ql > r || qr < l) return 0;
    if(ql <= l && r <= qr){
      return segtree[o];
    }
    int ans = 0;
    int mid = ((r - l) >> 1) + l;
    if(ql <= mid){
      ans = max(ans, query(o << 1, l, mid, ql, qr));
    }
    if(mid < qr){
      ans = max(ans, query(o << 1 | 1, mid + 1, r, ql, qr));
    }
    return ans;
  }
  void modify(int o, int l, int r, int p, int val){
    if(l == r){
      segtree[o] = max(segtree[o], val);
      return;
    }
    int mid = ((r - l) >> 1) + l;
    if(p <= mid){
      modify(o << 1, l, mid, p, val);
    }else{
      modify(o << 1 | 1, mid + 1, r, p, val);
    }
    segtree[o] = max(segtree[o << 1], segtree[o << 1 | 1]);
  }
  int lengthOfLIS(vector<int>& nums, int k) {
    int n = (int)nums.size();
    int ans = 0;
    mx = *max_element(nums.begin(), nums.end());
    segtree.resize(4 * mx + 1);
    for(int i=0;i<n;i++){
      int x = 1;
      if(nums[i] != 1){
        x = query(1, 1, mx, max(1, nums[i] - k), nums[i] - 1) + 1;
      }
      ans = max(ans, x);
      modify(1, 1, mx, nums[i], x);
    }
    return ans;
  }
};