最長増加部分列 (src/Misc/longest_increasing_subsequence.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-11 22:06:04+09:00
• Include: #include "src/Misc/longest_increasing_subsequence.hpp"

関数	概要	計算量
longest_increasing_subsequence(a, strict=true)	$\mathrm{idx}_i:=$ 添字 $i$ が LIS で使われる場合の LIS 上での位置(使われないなら $-1$ ) $\mathrm{cand}_j:=$ $\mathrm{idx}_i=j$ を満たす $i$ を昇順に並べた列 の二つを返す． 第二引数をfalseにすると広義単調増加数列を対象にする． 返り値は pair<vector<int>, veector<vector<int>>>	$O(n\log n)$

参考

https://miscalc.hatenablog.com/entry/2024/07/25/212618

Verified with

• test/atcoder/abc134_e.test.cpp
• test/atcoder/abc354_f.test.cpp
• test/atcoder/abc360_g.test.cpp
• test/yosupo/longest_increasing_subsequence.test.cpp
• test/yukicoder/1804.test.cpp
• test/yukicoder/992.test.cpp

Code

#pragma once
#include <vector>
#include <algorithm>
template <class T> std::pair<std::vector<int>, std::vector<std::vector<int>>> longest_increasing_subsequence(const std::vector<T> &a, bool strict= true) {
 int n= a.size();
 std::vector<int> idx(n);
 std::vector<T> dp(n);
 int len= 0;
 if (strict)
  for (int i= 0; i < n; ++i) {
   auto it= std::lower_bound(dp.begin(), dp.begin() + len, a[i]);
   if (*it= a[i]; (idx[i]= it - dp.begin()) == len) ++len;
  }
 else
  for (int i= 0; i < n; ++i) {
   auto it= std::upper_bound(dp.begin(), dp.begin() + len, a[i]);
   if (*it= a[i]; (idx[i]= it - dp.begin()) == len) ++len;
  }
 std::vector<std::vector<int>> cand(len);
 for (int i= n; i--;) {
  if (idx[i] == len - 1 || (!cand[idx[i] + 1].empty() && a[i] < a[cand[idx[i] + 1].back()])) cand[idx[i]].emplace_back(i);
  else idx[i]= -1;
 }
 for (auto &c: cand) std::reverse(c.begin(), c.end());
 return {idx, cand};
}

#line 2 "src/Misc/longest_increasing_subsequence.hpp"
#include <vector>
#include <algorithm>
template <class T> std::pair<std::vector<int>, std::vector<std::vector<int>>> longest_increasing_subsequence(const std::vector<T> &a, bool strict= true) {
 int n= a.size();
 std::vector<int> idx(n);
 std::vector<T> dp(n);
 int len= 0;
 if (strict)
  for (int i= 0; i < n; ++i) {
   auto it= std::lower_bound(dp.begin(), dp.begin() + len, a[i]);
   if (*it= a[i]; (idx[i]= it - dp.begin()) == len) ++len;
  }
 else
  for (int i= 0; i < n; ++i) {
   auto it= std::upper_bound(dp.begin(), dp.begin() + len, a[i]);
   if (*it= a[i]; (idx[i]= it - dp.begin()) == len) ++len;
  }
 std::vector<std::vector<int>> cand(len);
 for (int i= n; i--;) {
  if (idx[i] == len - 1 || (!cand[idx[i] + 1].empty() && a[i] < a[cand[idx[i] + 1].back()])) cand[idx[i]].emplace_back(i);
  else idx[i]= -1;
 }
 for (auto &c: cand) std::reverse(c.begin(), c.end());
 return {idx, cand};
}

Back to top page