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

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

形如这样:

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

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

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

朴素的解法（ n 2 n^2 n2）

拓扑序来解决

#include <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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

线段树

#include <bits/stdc++.h>
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 <bits/stdc++.h>
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;
}