LIS Variants

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Computes length of Longest Non-Decreasing Subsequence (LNDS)
5
// using patience sorting with upper_bound.
6
// For strict LIS, replace upper_bound with lower_bound.
7
8
int main() {
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    int n; 
13
    if (!(cin >> n)) return 0;
14
    vector<long long> a(n);
15
    for (int i = 0; i < n; ++i) cin >> a[i];
16
17
    vector<long long> tails; // tails[L-1] = minimal possible tail of an LNDS of length L
18
    tails.reserve(n);
19
20
    for (long long x : a) {
21
        // For LNDS, we can place x on the first pile with top > x (strictly greater)
22
        // so we use upper_bound over current pile tops.
23
        auto it = upper_bound(tails.begin(), tails.end(), x);
24
        if (it == tails.end()) {
25
            tails.push_back(x); // start a new pile (increase LNDS length)
26
        } else {
27
            *it = x; // make the pile top as small as possible
28
        }
29
    }
30
31
    cout << tails.size() << "\n";
32
    return 0;
33
}
34

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Node {
5
    int len;            // best length
6
    long long cnt;      // number of ways achieving best length
7
};
8
9
Node combine(const Node &a, const Node &b) {
10
    if (a.len > b.len) return a;
11
    if (b.len > a.len) return b;
12
    // Same length: sum counts
13
    return Node{a.len, a.cnt + b.cnt};
14
}
15
16
struct SegTree {
17
    int n;
18
    vector<Node> st;
19
    SegTree(int n_ = 0) { init(n_); }
20
    void init(int n_) {
21
        n = 1; while (n < n_) n <<= 1;
22
        st.assign(2*n, Node{0, 0}); // base: length 0, count 0
23
    }
24
    // point update: st[pos] = combine(st[pos], val)
25
    void update(int pos, Node val) {
26
        pos += n - 1;
27
        // merge at leaf: if new has larger length, replace; if equal, add counts
28
        if (st[pos].len < val.len) st[pos] = val;
29
        else if (st[pos].len == val.len) st[pos].cnt += val.cnt;
30
        // else keep existing
31
        pos >>= 1;
32
        while (pos) {
33
            st[pos] = combine(st[pos<<1], st[pos<<1|1]);
34
            pos >>= 1;
35
        }
36
    }
37
    // range query [1..r]
38
    Node query(int r) const {
39
        if (r <= 0) return Node{0, 0};
40
        int l = 1; r += n - 1; l += n - 1;
41
        Node left{0,0}, right{0,0};
42
        while (l <= r) {
43
            if ((l & 1) == 1) left = combine(left, st[l++]);
44
            if ((r & 1) == 0) right = combine(st[r--], right);
45
            l >>= 1; r >>= 1;
46
        }
47
        return combine(left, right);
48
    }
49
};
50
51
int main() {
52
    ios::sync_with_stdio(false);
53
    cin.tie(nullptr);
54
55
    int n; 
56
    if (!(cin >> n)) return 0;
57
    vector<long long> a(n);
58
    for (int i = 0; i < n; ++i) cin >> a[i];
59
60
    // Coordinate compression
61
    vector<long long> vals = a;
62
    sort(vals.begin(), vals.end());
63
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
64
    auto rankOf = [&](long long x){ return (int)(upper_bound(vals.begin(), vals.end(), x) - vals.begin()); }; // 1..M
65
66
    int M = (int)vals.size();
67
    SegTree st(M);
68
69
    for (int i = 0; i < n; ++i) {
70
        int r = rankOf(a[i]);
71
        // For LNDS, we can come from any value <= a[i], i.e., ranks in [1..r]
72
        Node best = st.query(r);
73
        // If no previous elements, start a new subsequence with count 1
74
        long long ways = (best.len == 0 ? 1LL : best.cnt);
75
        Node cur{best.len + 1, ways};
76
        st.update(r, cur);
77
    }
78
79
    Node ans = st.query(M);
80
    cout << ans.len << " " << ans.cnt << "\n";
81
    return 0;
82
}
83

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct SegTreeMax {
5
    int n; 
6
    vector<long long> st;
7
    void init(int n_) { n = 1; while (n < n_) n <<= 1; st.assign(2*n, 0LL); }
8
    // query max on [1..r]
9
    long long query(int r) const {
10
        if (r <= 0) return 0LL;
11
        int l = 1; r += n - 1; l += n - 1;
12
        long long L = 0, R = 0;
13
        while (l <= r) {
14
            if ((l & 1) == 1) L = max(L, st[l++]);
15
            if ((r & 1) == 0) R = max(st[r--], R);
16
            l >>= 1; r >>= 1;
17
        }
18
        return max(L, R);
19
    }
20
    void update(int pos, long long val) {
21
        pos += n - 1; 
22
        st[pos] = max(st[pos], val);
23
        pos >>= 1;
24
        while (pos) { st[pos] = max(st[pos<<1], st[pos<<1|1]); pos >>= 1; }
25
    }
26
};
27
28
int main(){
29
    ios::sync_with_stdio(false);
30
    cin.tie(nullptr);
31
32
    int n; if (!(cin >> n)) return 0;
33
    vector<long long> a(n);
34
    for (int i = 0; i < n; ++i) cin >> a[i];
35
36
    // Coordinate compression
37
    vector<long long> v = a;
38
    sort(v.begin(), v.end());
39
    v.erase(unique(v.begin(), v.end()), v.end());
40
    auto rankOf = [&](long long x){ return (int)(upper_bound(v.begin(), v.end(), x) - v.begin()); };
41
42
    SegTreeMax st; st.init((int)v.size());
43
    long long best = 0;
44
    for (int i = 0; i < n; ++i) {
45
        int r = rankOf(a[i]);
46
        // For non-decreasing sums, we can come from any value <= a[i]
47
        long long pref = st.query(r);
48
        long long cur = pref + a[i];
49
        st.update(r, cur);
50
        best = max(best, cur);
51
    }
52
53
    cout << best << "\n";
54
    return 0;
55
}
56

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Returns the minimum number of non-decreasing subsequences needed
5
// to partition the array (chain cover size under <=).
6
// Greedy: maintain pile tops; place x on the first pile with top > x,
7
// else start a new pile. Number of piles is optimal.
8
9
int main(){
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    int n; if (!(cin >> n)) return 0;
14
    vector<long long> a(n);
15
    for (int i = 0; i < n; ++i) cin >> a[i];
16
17
    multiset<long long> piles; // pile tops
18
    for (long long x : a) {
19
        auto it = piles.upper_bound(x); // first top > x
20
        if (it != piles.end()) {
21
            piles.erase(it);
22
        }
23
        piles.insert(x);
24
    }
25
    cout << piles.size() << "\n"; // equals length of the longest decreasing subsequence
26
    return 0;
27
}
28