CP-Algorithms Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub cp-algorithms/cp-algorithms-aux

:heavy_check_mark: Longest Increasing Subsequence (verify/structures/fenwick/lis.test.cpp)

Depends on

Code

// @brief Longest Increasing Subsequence
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"
#pragma GCC optimize("Ofast,unroll-loops")
#include "cp-algo/structures/fenwick.hpp"
#include "cp-algo/util/compress_coords.hpp"
#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<reference_wrapper<int>> coords;
    vector<int> a(n);
    for(auto &it: a) {
        cin >> it;
        coords.push_back(ref(it));
    }
    auto b = cp_algo::compress_coords(coords);
    struct longest {
        int len = 0, last = 0;
        auto operator <=>(longest const&) const = default;
    };
    cp_algo::structures::fenwick_max me(vector<longest>(n + 1));
    vector<int> pre(n);
    for(auto [i, it]: a | views::enumerate) {
        auto [len, last] = me.prefix_fold(it);
        me.update(it, {len + 1, (int)i});
        pre[i] = last;
    }
    auto [len, last] = me.prefix_fold(n);
    cout << len << '\n';
    vector<int> ans(len);
    while(len--) {
        ans[len] = last;
        last = pre[last];
    }
    for(auto it: ans) {
        cout << it << ' ';
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; 
    t = 1;// cin >> t;
    while(t--) {
        solve();
    }
}
 
#line 1 "verify/structures/fenwick/lis.test.cpp"
// @brief Longest Increasing Subsequence
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"
#pragma GCC optimize("Ofast,unroll-loops")
#line 1 "cp-algo/structures/fenwick.hpp"


#include <cassert>
#include <vector>
namespace cp_algo::structures {
    template <typename Op>
    struct inverse_op {};

    template <typename T>
    struct inverse_op<std::plus<T>> {
        static T apply(T const& a, T const& b) {
            return a - b;
        }
    };

    template <typename T>
    struct inverse_op<std::multiplies<T>> {
        static T apply(T const& a, T const& b) {
            return a / b;
        }
    };

    template<typename T, std::ranges::range Container = std::vector<T>, typename Op = std::plus<T>>
    struct fenwick {
        Op op;
        size_t n;
        Container data;

        fenwick(auto &&range, Op &&op = Op{}): op(std::move(op)) {
            assign(std::move(range));
        }
        void to_prefix_folds() {
            for(size_t i = 1; i < n; i++) {
                if(i + (i & -i) <= n) {
                    data[i + (i & -i)] = op(data[i + (i & -i)], data[i]);
                }
            }
        }
        void assign(auto &&range) {
            n = size(range) - 1;
            data = std::move(range);
            to_prefix_folds();
        }
        void update(size_t x, T const& v) {
            for(++x; x <= n; x += x & -x) {
                data[x] = op(data[x], v);
            }
        }
        // fold of [0, r)
        T prefix_fold(size_t r) const {
            assert(r <= n);
            T res = {};
            for(; r; r -= r & -r) {
                res = op(res, data[r]);
            }
            return res;
        }
        // fold of [l, r)
        T range_fold(size_t l, size_t r) const {
            return inverse_op<Op>::apply(prefix_fold(r), prefix_fold(l));
        }
        // Last x s.t. prefix_fold(x) <= k
        // Assumes prefix_fold is monotonic
        // returns [x, prefix_fold(x)]
        auto prefix_lower_bound(T k) const {
            size_t x = 0;
            T pref = {};
            for(size_t i = std::bit_floor(n); i; i /= 2) {
                if(x + i <= n && op(pref, data[x + i]) <= k) {
                    pref = op(pref, data[x + i]);
                    x += i;
                }
            }
            return std::pair{x, pref};
        }
    };

    template<std::ranges::range Container, typename Op>
    fenwick(Container&&, Op&&) -> fenwick<std::ranges::range_value_t<Container>, Container, Op>;
    template<std::ranges::range Container>
    fenwick(Container&&) -> fenwick<std::ranges::range_value_t<Container>, Container>;

    auto maxer = [](auto const& a, auto const& b) {
        return std::max(a, b);
    };
    template<typename T, std::ranges::range Container = std::vector<T>>
    struct fenwick_max: fenwick<T, Container, decltype(maxer)> {
        using fenwick<T, Container, decltype(maxer)>::fenwick;
    };
    template<std::ranges::range Container>
    fenwick_max(Container&&) -> fenwick_max<std::ranges::range_value_t<Container>, Container>;

}

#line 1 "cp-algo/util/compress_coords.hpp"


#line 1 "cp-algo/util/sort.hpp"


#line 1 "cp-algo/util/bit.hpp"


#include <immintrin.h>
#include <cstdint>
#include <array>
#include <bit>
namespace cp_algo {
    template<typename Uint>
    constexpr size_t bit_width = sizeof(Uint) * 8;

    size_t order_of_bit(auto x, size_t k) {
        return k ? std::popcount(x << (bit_width<decltype(x)> - k)) : 0;
    }
    [[gnu::target("bmi2")]]
    size_t kth_set_bit(uint64_t x, size_t k) {
        return std::countr_zero(_pdep_u64(1ULL << k, x));
    }
    template<int fl = 0>
    void with_bit_floor(size_t n, auto &&callback) {
        if constexpr (fl >= 63) {
            return;
        } else if (n >> (fl + 1)) {
            with_bit_floor<fl + 1>(n, callback);
        } else {
            callback.template operator()<1ULL << fl>();
        }
    }
}

#line 4 "cp-algo/util/sort.hpp"
#include <algorithm>
#include <numeric>
#include <ranges>
#line 8 "cp-algo/util/sort.hpp"
namespace cp_algo {
    template<size_t maxc>
    void count_sort(auto &a, auto &&proj = std::identity{}) {
        std::array<int, maxc> cnt = {};
        for(auto &x: a) {
            cnt[proj(x)]++;
        }
        std::partial_sum(begin(cnt), end(cnt), begin(cnt));
        auto res = a;
        for(auto const& it: a | std::views::reverse) {
            res[--cnt[proj(it)]] = it;
        }
        a = std::move(res);
    }

    void radix_sort(auto &a) {
        if(empty(a)) {
            return;
        }
        auto [mn, mx] = std::ranges::minmax(a);
        with_bit_floor<1>(size(a), [&]<size_t floor>() {
            constexpr int base = std::min<size_t>(floor, 1 << 16);
            for(int64_t i = 1; i <= mx - mn; i *= base) {
                count_sort<base>(a, [&](auto x) {
                    return (x - mn) / i % base;
                });
            }
        });
    }
}

#line 5 "cp-algo/util/compress_coords.hpp"
namespace cp_algo {
    // coords is a range of reference_wrapper<T>
    auto compress_coords(auto &&coords) {
        using T = std::decay_t<std::unwrap_reference_t<
            std::ranges::range_value_t<decltype(coords)>
        >>;
        std::vector<T> original;
        if(empty(coords)) {
            return original;
        }
        original.reserve(size(coords));
        radix_sort(coords);
        int idx = -1;
        T prev = ~coords.front();
        for(auto &x: coords) {
            if(x != prev) {
                idx++;
                prev = x;
                original.push_back(x);
            }
            x.get() = idx;
        }
        return original;
    }
}

#line 6 "verify/structures/fenwick/lis.test.cpp"
#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<reference_wrapper<int>> coords;
    vector<int> a(n);
    for(auto &it: a) {
        cin >> it;
        coords.push_back(ref(it));
    }
    auto b = cp_algo::compress_coords(coords);
    struct longest {
        int len = 0, last = 0;
        auto operator <=>(longest const&) const = default;
    };
    cp_algo::structures::fenwick_max me(vector<longest>(n + 1));
    vector<int> pre(n);
    for(auto [i, it]: a | views::enumerate) {
        auto [len, last] = me.prefix_fold(it);
        me.update(it, {len + 1, (int)i});
        pre[i] = last;
    }
    auto [len, last] = me.prefix_fold(n);
    cout << len << '\n';
    vector<int> ans(len);
    while(len--) {
        ans[len] = last;
        last = pre[last];
    }
    for(auto it: ans) {
        cout << it << ' ';
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; 
    t = 1;// cin >> t;
    while(t--) {
        solve();
    }
}

Test cases

Env Name Status Elapsed Memory
g++ example_00 :heavy_check_mark: AC 5 ms 4 MB
g++ example_01 :heavy_check_mark: AC 4 ms 4 MB
g++ hand_max_00 :heavy_check_mark: AC 77 ms 19 MB
g++ hand_min_00 :heavy_check_mark: AC 63 ms 17 MB
g++ max_random_00 :heavy_check_mark: AC 94 ms 17 MB
g++ max_random_01 :heavy_check_mark: AC 95 ms 17 MB
g++ max_random_02 :heavy_check_mark: AC 94 ms 17 MB
g++ max_random_03 :heavy_check_mark: AC 95 ms 17 MB
g++ max_random_04 :heavy_check_mark: AC 95 ms 17 MB
g++ random_00 :heavy_check_mark: AC 75 ms 14 MB
g++ random_01 :heavy_check_mark: AC 89 ms 16 MB
g++ random_02 :heavy_check_mark: AC 14 ms 5 MB
g++ random_03 :heavy_check_mark: AC 81 ms 15 MB
g++ random_04 :heavy_check_mark: AC 55 ms 11 MB
g++ small_00 :heavy_check_mark: AC 5 ms 4 MB
g++ small_01 :heavy_check_mark: AC 5 ms 4 MB
g++ small_02 :heavy_check_mark: AC 4 ms 4 MB
g++ small_03 :heavy_check_mark: AC 4 ms 4 MB
g++ small_04 :heavy_check_mark: AC 4 ms 4 MB
Back to top page