This documentation is automatically generated by online-judge-tools/verification-helper
#include "../longest_increasing_subsequence.hpp"
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"
#include <cassert>
#include <iostream>
using namespace std;
int main() {
cin.tie(nullptr), ios::sync_with_stdio(false);
int N;
cin >> N;
std::vector<int> A(N);
for (auto &x : A) cin >> x;
auto lis_idxs = longest_increasing_subsequence(A, LisType::StrictlyIncreasing).get_lis_indices();
assert(lis_idxs.size() == lis_length(A, LisType::StrictlyIncreasing));
cout << lis_idxs.size() << '\n';
for (auto i : lis_idxs) cout << i << ' ';
cout << '\n';
}
#line 2 "other_algorithms/longest_increasing_subsequence.hpp"
#include <algorithm>
#include <memory>
#include <vector>
enum class LisType {
StrictlyIncreasing,
Nondecreasing,
};
// Calculate (only) length of longest increasing subsequence (LIS)
// Complexity: O(n log n)
template <class T>
int lis_length(const std::vector<T> &seq, LisType lis_type = LisType::StrictlyIncreasing) {
std::vector<T> dp;
for (const T &x : seq) {
if (auto itr = (lis_type == LisType::StrictlyIncreasing
? std::lower_bound(begin(dp), end(dp), x)
: std::upper_bound(begin(dp), end(dp), x));
itr == end(dp)) {
dp.push_back(x);
} else {
*itr = x;
}
}
return dp.size();
}
template <class T> struct longest_increasing_subsequence {
LisType lis_type_ = LisType::StrictlyIncreasing;
int current_idx = 0;
struct Node {
std::shared_ptr<Node> par;
int len, idx;
T v;
};
std::vector<T> dp;
std::vector<std::shared_ptr<Node>> ptrs;
// Complexity: O(1)
longest_increasing_subsequence(LisType lis_type) : lis_type_(lis_type) {}
// Complexity: O(N log N)
longest_increasing_subsequence(const std::vector<T> &seq, LisType lis_type)
: lis_type_(lis_type) {
for (const T &x : seq) add(x);
}
// Complexity: O(log N)
std::shared_ptr<Node> add(const T &x) {
auto itr =
(lis_type_ == LisType::StrictlyIncreasing ? std::lower_bound(begin(dp), end(dp), x)
: std::upper_bound(begin(dp), end(dp), x));
int cur = std::distance(begin(dp), itr);
std::shared_ptr<Node> prv = (begin(dp) == itr ? nullptr : ptrs.at(cur - 1));
std::shared_ptr<Node> node(
new Node{prv, (prv == nullptr ? 0 : prv->len) + 1, current_idx++, x});
if (itr == end(dp)) {
dp.push_back(x), ptrs.push_back(node);
} else {
dp.at(cur) = x, ptrs.at(cur) = node;
}
return node;
}
std::shared_ptr<Node> head() const { return ptrs.empty() ? nullptr : ptrs.back(); }
// LIS をなす添字列を出力
// Complexity: O(N)
std::vector<int> get_lis_indices() const {
std::vector<int> ret;
for (auto ptr = head(); ptr != nullptr; ptr = ptr->par) ret.push_back(ptr->idx);
std::reverse(ret.begin(), ret.end());
return ret;
}
};
#line 2 "other_algorithms/test/longest_increasing_subsequence.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"
#include <cassert>
#include <iostream>
using namespace std;
int main() {
cin.tie(nullptr), ios::sync_with_stdio(false);
int N;
cin >> N;
std::vector<int> A(N);
for (auto &x : A) cin >> x;
auto lis_idxs = longest_increasing_subsequence(A, LisType::StrictlyIncreasing).get_lis_indices();
assert(lis_idxs.size() == lis_length(A, LisType::StrictlyIncreasing));
cout << lis_idxs.size() << '\n';
for (auto i : lis_idxs) cout << i << ' ';
cout << '\n';
}