LIS Algorithm
The Longest Increasing Subsequence (LIS) algorithm is a dynamic programming technique used to find the longest subsequence of a given sequence, in which the elements are in sorted order (increasing order) and the subsequence is not necessarily contiguous. This algorithm is particularly useful in fields such as computer science, bioinformatics, and data analysis, where it is often necessary to identify patterns or trends within large sets of data. The LIS algorithm can be applied to various types of sequences, such as numerical sequences, strings, or even more complex data structures. The primary goal of the algorithm is to identify the longest subsequence where the elements are in increasing order, as this can provide valuable insights into the underlying structure or pattern of the data.
The LIS algorithm works by iterating through each element in the input sequence and maintaining an array of the longest increasing subsequences found so far. For each element, the algorithm checks whether it can be appended to an existing subsequence or if it should start a new subsequence. The key to the efficiency of the algorithm is the use of dynamic programming, which allows for a more efficient solution by breaking down the problem into smaller overlapping subproblems and storing their solutions for reuse. This "bottom-up" approach enables the algorithm to build an optimal solution by solving smaller instances of the problem, ultimately resulting in a more efficient and effective solution. The time complexity of the LIS algorithm can be reduced to O(n log n) using binary search, making it suitable for handling large datasets.
/****************************************************************************************************
Finding Longest Increasing Sequence in O(NlogN)
About it: http://e-maxx.ru/algo/longest_increasing_subseq_log
Based on problem http://informatics.mccme.ru/mod/statements/view3.php?id=766&chapterid=1794
****************************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int MAXN = 105000;
const int INF = 1000 * 1000 * 1000;
int n;
int k, b, m;
int a[MAXN];
int d[MAXN];
int ind[MAXN], pr[MAXN];
vector <int> ansv;
int ans = 1;
int main() {
//assert(freopen("input.txt","r",stdin));
//assert(freopen("output.txt","w",stdout));
scanf("%d", &n);
scanf("%d %d %d %d", &a[1], &k, &b, &m);
for (int i = 2; i <= n; i++)
a[i] = (k * a[i - 1] + b) % m;
d[0] = -INF;
for (int i = 1; i <= n; i++)
d[i] = INF;
for (int i = 1; i <= n; i++) {
int pos = upper_bound(d + 1, d + n + 1, a[i]) - d;
if (d[pos - 1] < a[i] && a[i] < d[pos]) {
d[pos] = a[i];
ind[pos] = i;
pr[i] = ind[pos - 1];
if (pos > ans) {
ans = pos;
}
}
}
if (ans == 1) {
printf("%d", a[1]);
}
else {
int cur = ind[ans];
while (cur != 0) {
ansv.push_back(a[cur]);
cur = pr[cur];
}
for (int i = (int) ansv.size() - 1; i >= 0; i--)
printf("%d ", ansv[i]);
}
return 0;
}
