最长上升子序列 + 优化(线段树、树状数组)

最长上升子序列是一个我们很熟悉的东西了

形如这样:

给定一个长度为 N 的整数序列 a 1 , a 2 , … , a N 。 给定一个长度为 N 的整数序列 a_1,a_2,…,a_N。 给定一个长度为N的整数序列a1​,a2​,…,aN​。

请你计算该序列的最长上升子序列的长度。 请你计算该序列的最长上升子序列的长度。 请你计算该序列的最长上升子序列的长度。

上升子序列是指数值严格单调递增的子序列。 上升子序列是指数值严格单调递增的子序列。 上升子序列是指数值严格单调递增的子序列。

朴素的解法（ n 2 n^2 n2） 拓扑序来解决

对于这样一个问题，我们可以以当前的最长上升子序列推出下一个位置的最长上升子序列
显然，我们是可以进行这样的 *** 作的，递推进入下一步
就形如 i f     a r r [ i ] > a r r [ j ]     t h e n      a n s [ i ] = a n s [ j ] + 1 if \ \ \ arr[i] > arr[j] \ \ \ then \ \ \ \ ans[i] = ans[j] + 1 if   arr[i]>arr[j]   then    ans[i]=ans[j]+1
对于上面这样的状态转移不难推出，就是相当于对于每一个数字，都去做一遍dfs，去遍历到他可能出现的位置
比如 1 7 3 5 9 4 8，从 1 开始的位置有 7 3 5 9 4 8, 从7开始的位置有9 8,依次类推
其实上述的逐步推进有一点像拓扑排序，所以，我们可以把代码写出这个样子

#include 
using std::cin, std::cout, std::vector, std::queue;
int main() {
  int n, res = 0;
  cin >> n;
  vector<vector<int>> tree(n + 1, vector<int>());
  vector<int> in(n + 1), ans(n + 1, 0), ve(n + 1);
  queue<int> que;
  for (int i = 1; i <= n; i ++) cin >> ve[i];
  for (int i = 1; i <= n; i ++) 
    for (int j = i + 1; j <= n; j ++) 
      if (ve[j] > ve[i]) tree[i].push_back(j), in[j] ++;  
  for (int i = 1; i <= n; i ++) 
    if (!in[i]) que.push(i), ans[i] = 1;
  while (que.size()) {
    int u = que.front(); que.pop();
    res = std::max(res, ans[u]);
    for (int v : tree[u]) {
      ans[v] = std::max(ans[v], ans[u] + 1);
      if (!--in[v]) que.push(v);
    }
  }
  cout << res << "\n";
  return 0;
}

改成数组

上述做法有点浪费空间，需要建立一颗树
然后在树上面进行拓扑序，其实我们可以用数组来模拟这个拓扑序

#include 
using std::cin, std::cout, std::vector;
int main() {
  int n;
  cin >> n;
  vector<int> ve(n + 1), dp(n + 1, 1);
  for (int i = 1; i <= n; i++)
    cin >> ve[i];
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++)
      if (ve[i] < ve[j])
        dp[j] = std::max(dp[j], dp[i] + 1);
    ans = std::max(ans, dp[i]);
  }
  cout << ans << "\n";
  return 0;
}

好，动态规划，出来了。
其实动态规划本质上也是一个图上的拓扑序嘛，可以看出来
那么，我们可以把上述的遍历再改动一下，改成每一个数去寻找前面所有序列中满足条件的，且最大的

#include 
using std::cin, std::cout, std::vector;
int main() {
  int n;
  cin >> n;
  vector<int> ve(n + 1), dp(n + 1, 1);
  for (int i = 1; i <= n; i++)
    cin >> ve[i];
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++)
      if (ve[i] > ve[j])
        dp[i] = std::max(dp[i], dp[j] + 1);
    ans = std::max(ans, dp[i]);
  }
  cout << ans << "\n";
  return 0;
}

优化 n l o n g n nlongn nlongn

上述的解法中，最后我们使用了一种以当前位置为结尾的，去寻找前面满足条件的最长的子序列的答案
那么写出来，就类似于这种 d p [ i ] = m a x ( d p [ 1 ] , . . . , d p [ i − 1 ] ) + 1 dp[i] = max(dp[1], ..., dp[i-1]) + 1 dp[i]=max(dp[1],...,dp[i−1])+1 这样的形式
那么，我们只要想办法去找到一种可行的办法，来把枚举
满足条件的最大值 1 1 1 ~ i − 1 i-1 i−1 的时间 o ( n ) o(n) o(n)优化一下，那么整体的时间复杂度就降下来了

我们可以按值域来进行区分不同值结尾的最大的子序列
这样，要查询当前值为k时的最长的子序列就为 q u e r y ( 0 , k − 1 ) + 1 query(0, k-1) + 1 query(0,k−1)+1这样的形式
这样的信息，线段树和树状数组都可以维护

现在我们的需求是单点修改某一个位置的值，区间查询一块区域内的最大值
在这里，我们每一个点的值，指的是以当前位置下标为结尾的子序列的最大长度

线段树

利用线段树直接来维护一段值域里面的最大值

#include 
using std::cin, std::cout, std::vector;
int main() {
  int n, ans = 0;
  cin >> n;
  vector<int> ve(n), s(n);
  struct tr {
    int v, l, r;
  };
  vector<tr> tree(n * 4);
  std::function<void(int, int, int)> build = [&](int u, int l, int r) {
    tree[u] = tr{0, l, r};
    if (l == r)
      return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
  };
  std::function<void(int, int, int)> insert = [&](int u, int x, int v) {
    if (tree[u].l == tree[u].r) {
      tree[u].v = std::max(tree[u].v, v);
      return;
    }
    int mid = (tree[u].l + tree[u].r) >> 1;
    if (x <= mid)
      insert(u << 1, x, v);
    else
      insert(u << 1 | 1, x, v);
    tree[u].v =
        std::max(tree[u].v, std::max(tree[u << 1].v, tree[u << 1 | 1].v));
  };
  std::function<int(int, int, int)> query = [&](int u, int l, int r) {
    if (l > r) return 0;
    if (l <= tree[u].l && tree[u].r <= r)
      return tree[u].v;
    int mid = (tree[u].l + tree[u].r) >> 1, a{}, b{};
    if (l <= mid)
      a = query(u << 1, l, r);
    if (r > mid)
      b = query(u << 1 | 1, l, r);
    return std::max(a, b);
  };
  for (int i = 0; i < n; i++)
    cin >> ve[i], s[i] = ve[i];
  std::sort(begin(s), end(s));
  s.erase(std::unique(begin(s), end(s)), s.end());
  for (int i = 0; i < n; i++)
    ve[i] = std::lower_bound(begin(s), end(s), ve[i]) - s.begin() + 1;
    
  build(1, 1, s.size());
  for (int i = 0; i < n; i++) 
    insert(1, ve[i], query(1, 1, ve[i] - 1) + 1);
  cout << query(1, 1, s.size());
  return 0;
}

树状数组

树状数组写着要少不少，但是没有那么易懂

#include 
using std::cin, std::cout, std::vector;
int main() {
  int n, ans = 0;
  cin >> n;
  vector<int> ve(n), s(n);
  vector<int> tr(n + 1), ma(n + 1);
  auto low = [](int x) { return x & (-x); };
  auto insert = [&](int x, int v) {
    tr[x] = v;
    while (x <= n) {
      ma[x] = std::max(v, ma[x]);
      for (int i = 1; i < low(x); i <<= 1)
        ma[x] = std::max(ma[x], ma[x - i]);
      x += low(x);
    }
  };
  auto query = [&](int l, int r) {
    int res = 0;
    while (r >= l) {
      res = std::max(tr[r], res);
      r--;
      for (; r - low(r) >= l; r -= low(r))
        res = std::max(ma[r], res);
    }
    return res;
  };
  for (int i = 0; i < n; i++)
    cin >> ve[i], s[i] = ve[i];
  std::sort(begin(s), end(s));
  s.erase(std::unique(begin(s), end(s)), s.end());
  for (int i = 0; i < n; i++)
    ve[i] = std::lower_bound(begin(s), end(s), ve[i]) - s.begin() + 1;
  for (int i = 0; i < n; i ++) {
    insert(ve[i], query(1, ve[i] - 1) + 1);
  }
  cout << query(1, s.size());
  return 0;
}