cp-reference-codes/src/8-misc/seq_lis.cpp at main · manoflearning/cp-reference-codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include"../0-common/common.hpp"

// what: compute LIS length and reconstruct one increasing subsequence.
// time: O(n log n); memory: O(n)
// constraint: use lower_bound for strict; use upper_bound for non-decreasing.
// usage: int len = lis_len(a); auto seq = lis_seq(a);

intlis_len(const vector<ll> &a) {
// result: length of LIS.
 vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(all(tail), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
 }
returnsz(tail);
}

vector<ll> lis_seq(const vector<ll> &a) {
// result: one LIS sequence.
int n = sz(a);
 vector<ll> tail;
 vector<int> tail_idx;
 vector<int> pre(n, -1);
for (int i = 0; i < n; i++) {
 ll x = a[i];
int pos = lower_bound(all(tail), x) - tail.begin();
if (pos == sz(tail)) {
 tail.push_back(x);
 tail_idx.push_back(i);
 } else {
 tail[pos] = x;
 tail_idx[pos] = i;
 }
if (pos > 0) pre[i] = tail_idx[pos - 1];
 }
 vector<ll> ret;
int cur = tail_idx.empty() ? -1 : tail_idx.back();
while (cur != -1) {
 ret.push_back(a[cur]);
 cur = pre[cur];
 }
reverse(all(ret));
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include"../0-common/common.hpp"

// what: compute LIS length and reconstruct one increasing subsequence.
// time: O(n log n); memory: O(n)
// constraint: use lower_bound for strict; use upper_bound for non-decreasing.
// usage: int len = lis_len(a); auto seq = lis_seq(a);

intlis_len(const vector<ll> &a) {
// result: length of LIS.
 vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(all(tail), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
 }
returnsz(tail);
}

vector<ll> lis_seq(const vector<ll> &a) {
// result: one LIS sequence.
int n = sz(a);
 vector<ll> tail;
 vector<int> tail_idx;
 vector<int> pre(n, -1);
for (int i = 0; i < n; i++) {
 ll x = a[i];
int pos = lower_bound(all(tail), x) - tail.begin();
if (pos == sz(tail)) {
 tail.push_back(x);
 tail_idx.push_back(i);
 } else {
 tail[pos] = x;
 tail_idx[pos] = i;
 }
if (pos > 0) pre[i] = tail_idx[pos - 1];
 }
 vector<ll> ret;
int cur = tail_idx.empty() ? -1 : tail_idx.back();
while (cur != -1) {
 ret.push_back(a[cur]);
 cur = pre[cur];
 }
reverse(all(ret));
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include"../0-common/common.hpp"

// what: compute LIS length and reconstruct one increasing subsequence.
// time: O(n log n); memory: O(n)
// constraint: use lower_bound for strict; use upper_bound for non-decreasing.
// usage: int len = lis_len(a); auto seq = lis_seq(a);

intlis_len(const vector<ll> &a) {
// result: length of LIS.
 vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(all(tail), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
 }
returnsz(tail);
}

vector<ll> lis_seq(const vector<ll> &a) {
// result: one LIS sequence.
int n = sz(a);
 vector<ll> tail;
 vector<int> tail_idx;
 vector<int> pre(n, -1);
for (int i = 0; i < n; i++) {
 ll x = a[i];
int pos = lower_bound(all(tail), x) - tail.begin();
if (pos == sz(tail)) {
 tail.push_back(x);
 tail_idx.push_back(i);
 } else {
 tail[pos] = x;
 tail_idx[pos] = i;
 }
if (pos > 0) pre[i] = tail_idx[pos - 1];
 }
 vector<ll> ret;
int cur = tail_idx.empty() ? -1 : tail_idx.back();
while (cur != -1) {
 ret.push_back(a[cur]);
 cur = pre[cur];
 }
reverse(all(ret));
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include"../0-common/common.hpp"

// what: compute LIS length and reconstruct one increasing subsequence.
// time: O(n log n); memory: O(n)
// constraint: use lower_bound for strict; use upper_bound for non-decreasing.
// usage: int len = lis_len(a); auto seq = lis_seq(a);

intlis_len(const vector<ll> &a) {
// result: length of LIS.
 vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(all(tail), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
 }
returnsz(tail);
}

vector<ll> lis_seq(const vector<ll> &a) {
// result: one LIS sequence.
int n = sz(a);
 vector<ll> tail;
 vector<int> tail_idx;
 vector<int> pre(n, -1);
for (int i = 0; i < n; i++) {
 ll x = a[i];
int pos = lower_bound(all(tail), x) - tail.begin();
if (pos == sz(tail)) {
 tail.push_back(x);
 tail_idx.push_back(i);
 } else {
 tail[pos] = x;
 tail_idx[pos] = i;
 }
if (pos > 0) pre[i] = tail_idx[pos - 1];
 }
 vector<ll> ret;
int cur = tail_idx.empty() ? -1 : tail_idx.back();
while (cur != -1) {
 ret.push_back(a[cur]);
 cur = pre[cur];
 }
reverse(all(ret));
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include"../0-common/common.hpp"

// what: compute LIS length and reconstruct one increasing subsequence.
// time: O(n log n); memory: O(n)
// constraint: use lower_bound for strict; use upper_bound for non-decreasing.
// usage: int len = lis_len(a); auto seq = lis_seq(a);

intlis_len(const vector<ll> &a) {
// result: length of LIS.
 vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(all(tail), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
 }
returnsz(tail);
}

vector<ll> lis_seq(const vector<ll> &a) {
// result: one LIS sequence.
int n = sz(a);
 vector<ll> tail;
 vector<int> tail_idx;
 vector<int> pre(n, -1);
for (int i = 0; i < n; i++) {
 ll x = a[i];
int pos = lower_bound(all(tail), x) - tail.begin();
if (pos == sz(tail)) {
 tail.push_back(x);
 tail_idx.push_back(i);
 } else {
 tail[pos] = x;
 tail_idx[pos] = i;
 }
if (pos > 0) pre[i] = tail_idx[pos - 1];
 }
 vector<ll> ret;
int cur = tail_idx.empty() ? -1 : tail_idx.back();
while (cur != -1) {
 ret.push_back(a[cur]);
 cur = pre[cur];
 }
reverse(all(ret));
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include"../0-common/common.hpp"

// what: compute LIS length and reconstruct one increasing subsequence.
// time: O(n log n); memory: O(n)
// constraint: use lower_bound for strict; use upper_bound for non-decreasing.
// usage: int len = lis_len(a); auto seq = lis_seq(a);

intlis_len(const vector<ll> &a) {
// result: length of LIS.
 vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(all(tail), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
 }
returnsz(tail);
}

vector<ll> lis_seq(const vector<ll> &a) {
// result: one LIS sequence.
int n = sz(a);
 vector<ll> tail;
 vector<int> tail_idx;
 vector<int> pre(n, -1);
for (int i = 0; i < n; i++) {
 ll x = a[i];
int pos = lower_bound(all(tail), x) - tail.begin();
if (pos == sz(tail)) {
 tail.push_back(x);
 tail_idx.push_back(i);
 } else {
 tail[pos] = x;
 tail_idx[pos] = i;
 }
if (pos > 0) pre[i] = tail_idx[pos - 1];
 }
 vector<ll> ret;
int cur = tail_idx.empty() ? -1 : tail_idx.back();
while (cur != -1) {
 ret.push_back(a[cur]);
 cur = pre[cur];
 }
reverse(all(ret));
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include"../0-common/common.hpp"

// what: compute LIS length and reconstruct one increasing subsequence.
// time: O(n log n); memory: O(n)
// constraint: use lower_bound for strict; use upper_bound for non-decreasing.
// usage: int len = lis_len(a); auto seq = lis_seq(a);

intlis_len(const vector<ll> &a) {
// result: length of LIS.
 vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(all(tail), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
 }
returnsz(tail);
}

vector<ll> lis_seq(const vector<ll> &a) {
// result: one LIS sequence.
int n = sz(a);
 vector<ll> tail;
 vector<int> tail_idx;
 vector<int> pre(n, -1);
for (int i = 0; i < n; i++) {
 ll x = a[i];
int pos = lower_bound(all(tail), x) - tail.begin();
if (pos == sz(tail)) {
 tail.push_back(x);
 tail_idx.push_back(i);
 } else {
 tail[pos] = x;
 tail_idx[pos] = i;
 }
if (pos > 0) pre[i] = tail_idx[pos - 1];
 }
 vector<ll> ret;
int cur = tail_idx.empty() ? -1 : tail_idx.back();
while (cur != -1) {
 ret.push_back(a[cur]);
 cur = pre[cur];
 }
reverse(all(ret));
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include"../0-common/common.hpp"

// what: compute LIS length and reconstruct one increasing subsequence.
// time: O(n log n); memory: O(n)
// constraint: use lower_bound for strict; use upper_bound for non-decreasing.
// usage: int len = lis_len(a); auto seq = lis_seq(a);

intlis_len(const vector<ll> &a) {
// result: length of LIS.
 vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(all(tail), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
 }
returnsz(tail);
}

vector<ll> lis_seq(const vector<ll> &a) {
// result: one LIS sequence.
int n = sz(a);
 vector<ll> tail;
 vector<int> tail_idx;
 vector<int> pre(n, -1);
for (int i = 0; i < n; i++) {
 ll x = a[i];
int pos = lower_bound(all(tail), x) - tail.begin();
if (pos == sz(tail)) {
 tail.push_back(x);
 tail_idx.push_back(i);
 } else {
 tail[pos] = x;
 tail_idx[pos] = i;
 }
if (pos > 0) pre[i] = tail_idx[pos - 1];
 }
 vector<ll> ret;
int cur = tail_idx.empty() ? -1 : tail_idx.back();
while (cur != -1) {
 ret.push_back(a[cur]);
 cur = pre[cur];
 }
reverse(all(ret));
return ret;
}