# library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kazunetakahashi/library

# DP-Typical/LIS.cpp

## Code

#include <algorithm>
#include <iostream>
#include <limits>
#include <stack>
#include <vector>
using namespace std;
using ll = long long;

// ----- LIS -----

template <typename T>
class LIS
{
struct Cache_LIS
{
typename vector<T>::iterator it;
T value;
};

int n; // fixed
T infty;
vector<T> dp;
stack<Cache_LIS> st;

public:
LIS() {}
LIS(int n, T infty = numeric_limits<T>::max()) : n{n}, infty{infty}, dp(n, infty) {}

int query(T a)
{
auto it{lower_bound(dp.begin(), dp.end(), a)};
auto value{*it};
st.push(Cache_LIS{it, value});
*it = a;
return lower_bound(dp.begin(), dp.end(), infty) - dp.begin();
}

bool rollback()
{
if (st.empty())
{
return false;
}
auto const &c{st.top()};
*c.it = c.value;
st.pop();
return true;
}

private:
};



#line 1 "DP-Typical/LIS.cpp"
#include <algorithm>
#include <iostream>
#include <limits>
#include <stack>
#include <vector>
using namespace std;
using ll = long long;

// ----- LIS -----

template <typename T>
class LIS
{
struct Cache_LIS
{
typename vector<T>::iterator it;
T value;
};

int n; // fixed
T infty;
vector<T> dp;
stack<Cache_LIS> st;

public:
LIS() {}
LIS(int n, T infty = numeric_limits<T>::max()) : n{n}, infty{infty}, dp(n, infty) {}

int query(T a)
{
auto it{lower_bound(dp.begin(), dp.end(), a)};
auto value{*it};
st.push(Cache_LIS{it, value});
*it = a;
return lower_bound(dp.begin(), dp.end(), infty) - dp.begin();
}

bool rollback()
{
if (st.empty())
{
return false;
}
auto const &c{st.top()};
*c.it = c.value;
st.pop();
return true;
}

private:
};