m1une's library

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

View on GitHub

:warning: Sequence Algorithms All
(algo/sequence/all.hpp)

Overview

algo/sequence/all.hpp includes one-shot algorithms over arrays and sequences. The public namespace is m1une::algo.

Included Headers

Header Contents
algo/sequence/lis.hpp Longest increasing subsequence indices.
algo/sequence/inversion_count.hpp Inversion count by merge sort.
algo/sequence/merge_intervals.hpp Union of half-open intervals.
algo/sequence/non_adjacent_selection.hpp Maximum and minimum exact-count sums with no adjacent selections.
algo/sequence/number_of_subsequences.hpp Number of distinct nonempty subsequences.
algo/sequence/run_length_encoding.hpp Run-length encoding for consecutive equal values.
algo/sequence/subset_sum.hpp Meet-in-the-middle subset-sum helpers.

Depends on

Required by

Code

#ifndef M1UNE_ALGO_SEQUENCE_ALL_HPP
#define M1UNE_ALGO_SEQUENCE_ALL_HPP 1

#include "inversion_count.hpp"
#include "lis.hpp"
#include "merge_intervals.hpp"
#include "mex.hpp"
#include "non_adjacent_selection.hpp"
#include "number_of_subsequences.hpp"
#include "run_length_encoding.hpp"
#include "subset_sum.hpp"

#endif  // M1UNE_ALGO_SEQUENCE_ALL_HPP
#line 1 "algo/sequence/all.hpp"



#line 1 "algo/sequence/inversion_count.hpp"



#include <vector>

namespace m1une {
namespace algo {

// Returns the number of pairs (i, j) with i < j and a[i] > a[j].
// The vector is taken by value because merge sort rearranges it.
template <typename T>
long long inversion_count(std::vector<T> a) {
    const int n = int(a.size());
    std::vector<T> temp = a;

    auto merge_sort = [&](auto& self, int l, int r) -> long long {
        if (r - l <= 1) return 0;

        const int m = l + (r - l) / 2;
        long long inv = self(self, l, m) + self(self, m, r);

        int i = l;
        int j = m;
        int k = l;
        while (i < m && j < r) {
            if (!(a[j] < a[i])) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
                inv += m - i;
            }
        }

        while (i < m) temp[k++] = a[i++];
        while (j < r) temp[k++] = a[j++];

        for (int p = l; p < r; ++p) {
            a[p] = temp[p];
        }

        return inv;
    };

    return merge_sort(merge_sort, 0, n);
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/sequence/lis.hpp"



#include <algorithm>
#include <iterator>
#line 7 "algo/sequence/lis.hpp"

namespace m1une {
namespace algo {

// Returns the zero-based indices of a longest increasing subsequence.
// If `strict` is false, equal adjacent values are also allowed.
template <typename T>
std::vector<int> lis(const std::vector<T>& a, bool strict = true) {
    const int n = int(a.size());
    std::vector<T> tails;
    std::vector<int> tail_positions;
    std::vector<int> predecessor(n, -1);
    tails.reserve(n);
    tail_positions.reserve(n);

    for (int i = 0; i < n; ++i) {
        auto it = strict ? std::lower_bound(tails.begin(), tails.end(), a[i])
                         : std::upper_bound(tails.begin(), tails.end(), a[i]);
        const int length = int(std::distance(tails.begin(), it));

        if (it == tails.end()) {
            tails.push_back(a[i]);
            tail_positions.push_back(i);
        } else {
            *it = a[i];
            tail_positions[length] = i;
        }

        if (length > 0) {
            predecessor[i] = tail_positions[length - 1];
        }
    }

    if (tail_positions.empty()) return {};

    std::vector<int> result;
    result.reserve(tail_positions.size());
    int current = tail_positions.back();
    while (current != -1) {
        result.push_back(current);
        current = predecessor[current];
    }
    std::reverse(result.begin(), result.end());
    return result;
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/sequence/merge_intervals.hpp"



#line 5 "algo/sequence/merge_intervals.hpp"
#include <cassert>
#include <cstddef>
#include <utility>
#line 9 "algo/sequence/merge_intervals.hpp"

namespace m1une {
namespace algo {

// Returns the union of half-open intervals as sorted, disjoint intervals.
template <typename T>
std::vector<std::pair<T, T>> merge_intervals(
    std::vector<std::pair<T, T>> intervals
) {
    for (const auto& [left, right] : intervals) {
        if (right < left) assert(false);
    }

    std::sort(
        intervals.begin(),
        intervals.end(),
        [](const auto& lhs, const auto& rhs) {
            if (lhs.first < rhs.first) return true;
            if (rhs.first < lhs.first) return false;
            return lhs.second < rhs.second;
        }
    );

    std::size_t result_size = 0;
    for (std::size_t index = 0; index < intervals.size(); ++index) {
        auto& [left, right] = intervals[index];
        if (!(left < right)) continue;
        if (result_size == 0 || intervals[result_size - 1].second < left) {
            if (result_size != index) {
                intervals[result_size] = std::move(intervals[index]);
            }
            ++result_size;
        } else if (intervals[result_size - 1].second < right) {
            intervals[result_size - 1].second = std::move(right);
        }
    }
    intervals.erase(intervals.begin() + result_size, intervals.end());
    return intervals;
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/sequence/mex.hpp"



#line 5 "algo/sequence/mex.hpp"
#include <cstdint>
#include <limits>
#include <type_traits>
#line 9 "algo/sequence/mex.hpp"

namespace m1une {
namespace algo {

// Returns the smallest nonnegative integer absent from values.
template <class T>
int mex(const std::vector<T>& values) {
    static_assert(
        std::is_integral_v<T> && sizeof(T) <= sizeof(std::uintmax_t),
        "mex requires standard integral values"
    );
    assert(values.size() <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
    const int n = int(values.size());
    std::vector<unsigned char> present(n, 0);
    for (T value : values) {
        if constexpr (std::is_signed_v<T>) {
            if (value < 0) continue;
        }
        if (static_cast<std::uintmax_t>(value) < static_cast<std::uintmax_t>(n)) {
            present[int(value)] = 1;
        }
    }
    int answer = 0;
    while (answer < n && present[answer]) ++answer;
    return answer;
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/sequence/non_adjacent_selection.hpp"



#include <functional>
#include <queue>
#line 7 "algo/sequence/non_adjacent_selection.hpp"

namespace m1une {
namespace algo {

namespace detail {

template <typename T>
struct NonAdjacentSelectionEntry {
    T value;
    int index;
};

template <typename T, typename Better>
struct NonAdjacentSelectionCompare {
    Better better;

    bool operator()(
        const NonAdjacentSelectionEntry<T>& lhs,
        const NonAdjacentSelectionEntry<T>& rhs
    ) const {
        if (better(lhs.value, rhs.value)) return false;
        if (better(rhs.value, lhs.value)) return true;
        return lhs.index > rhs.index;
    }
};

template <typename T, typename Better>
std::vector<T> non_adjacent_selection_sums(const std::vector<T>& values, Better better) {
    const int n = int(values.size());
    std::vector<T> weight = values;
    std::vector<int> left(n), right(n);
    std::vector<char> alive(n, true);
    for (int i = 0; i < n; ++i) {
        left[i] = i - 1;
        right[i] = (i + 1 == n ? -1 : i + 1);
    }

    using Entry = NonAdjacentSelectionEntry<T>;
    using Compare = NonAdjacentSelectionCompare<T, Better>;
    std::priority_queue<Entry, std::vector<Entry>, Compare> heap(Compare{better});
    for (int i = 0; i < n; ++i) heap.push(Entry{weight[i], i});

    std::vector<T> result;
    result.reserve((n + 1) / 2);
    T sum{};
    while (int(result.size()) < (n + 1) / 2) {
        while (!alive[heap.top().index]) heap.pop();
        const int current = heap.top().index;
        heap.pop();

        sum += weight[current];
        result.push_back(sum);

        const int l = left[current];
        const int r = right[current];
        if (l != -1 && r != -1) {
            weight[current] = weight[l] + weight[r] - weight[current];

            const int ll = left[l];
            const int rr = right[r];
            alive[l] = false;
            alive[r] = false;
            left[current] = ll;
            right[current] = rr;
            if (ll != -1) right[ll] = current;
            if (rr != -1) left[rr] = current;
            heap.push(Entry{weight[current], current});
        } else {
            const int ll = (l == -1 ? -1 : left[l]);
            const int rr = (r == -1 ? -1 : right[r]);
            alive[current] = false;
            if (l != -1) alive[l] = false;
            if (r != -1) alive[r] = false;
            if (ll != -1) right[ll] = rr;
            if (rr != -1) left[rr] = ll;
        }
    }
    return result;
}

}  // namespace detail

// Entry k - 1 is the maximum sum obtained by selecting exactly k values, with
// no two selected indices adjacent.
template <typename T>
std::vector<T> maximum_non_adjacent_selection_sums(const std::vector<T>& values) {
    return detail::non_adjacent_selection_sums(values, std::greater<T>{});
}

// Entry k - 1 is the minimum sum obtained by selecting exactly k values, with
// no two selected indices adjacent.
template <typename T>
std::vector<T> minimum_non_adjacent_selection_sums(const std::vector<T>& values) {
    return detail::non_adjacent_selection_sums(values, std::less<T>{});
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/sequence/number_of_subsequences.hpp"



#line 6 "algo/sequence/number_of_subsequences.hpp"

namespace m1une {
namespace algo {

// Returns the number of distinct nonempty subsequences.
template <class Mint, class T>
Mint number_of_distinct_subsequences(const std::vector<T>& values) {
    std::vector<T> compressed = values;
    std::sort(compressed.begin(), compressed.end());
    compressed.erase(
        std::unique(compressed.begin(), compressed.end()),
        compressed.end()
    );

    std::vector<Mint> previous_total(compressed.size(), Mint(0));
    Mint total = 1;
    for (const T& value : values) {
        int rank = int(
            std::lower_bound(
                compressed.begin(),
                compressed.end(),
                value
            ) - compressed.begin()
        );
        Mint old_total = total;
        total = total + total - previous_total[rank];
        previous_total[rank] = old_total;
    }
    return total - Mint(1);
}

template <class Mint, class T>
Mint number_of_subsequences(const std::vector<T>& values) {
    return number_of_distinct_subsequences<Mint>(values);
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/sequence/run_length_encoding.hpp"



#line 7 "algo/sequence/run_length_encoding.hpp"

namespace m1une {
namespace algo {

template <typename Container>
auto run_length_encoding(const Container& values) {
    using T = typename Container::value_type;
    std::vector<std::pair<T, long long>> result;

    auto it = std::begin(values);
    auto last = std::end(values);
    if (it == last) {
        return result;
    }

    T current = *it;
    long long count = 0;
    for (; it != last; ++it) {
        if (*it == current) {
            ++count;
        } else {
            result.emplace_back(current, count);
            current = *it;
            count = 1;
        }
    }
    result.emplace_back(current, count);
    return result;
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/sequence/subset_sum.hpp"



#line 8 "algo/sequence/subset_sum.hpp"

namespace m1une {
namespace algo {

namespace internal {

template <typename T>
std::vector<T> enumerate_sorted_subset_sums(
    const std::vector<T>& values,
    int left,
    int right
) {
    std::vector<T> sums(1, T{});
    std::vector<T> merged;

    for (int i = left; i < right; ++i) {
        const std::size_t size = sums.size();
        merged.clear();
        merged.reserve(size * 2);

        std::size_t without = 0;
        std::size_t with = 0;
        while (without < size && with < size) {
            const T with_current = sums[with] + values[i];
            if (with_current < sums[without]) {
                merged.push_back(with_current);
                ++with;
            } else {
                merged.push_back(sums[without]);
                ++without;
            }
        }
        while (without < size) {
            merged.push_back(sums[without]);
            ++without;
        }
        while (with < size) {
            merged.push_back(sums[with] + values[i]);
            ++with;
        }
        sums.swap(merged);
    }

    return sums;
}

}  // namespace internal

// Returns the sorted subset sums of values[0, n / 2) and values[n / 2, n).
template <typename T>
std::pair<std::vector<T>, std::vector<T>> enumerate_half_subset_sums(
    const std::vector<T>& values
) {
    const int n = int(values.size());
    const int middle = n / 2;
    return {
        internal::enumerate_sorted_subset_sums(values, 0, middle),
        internal::enumerate_sorted_subset_sums(values, middle, n)
    };
}

// Returns the maximum subset sum not exceeding limit.
template <typename T>
T maximum_subset_sum(const std::vector<T>& values, const T& limit) {
    assert(!(limit < T{}));
    auto [left_sums, right_sums] = enumerate_half_subset_sums(values);

    T answer{};
    std::size_t right_count = right_sums.size();
    for (const T& left : left_sums) {
        while (
            right_count > 0 &&
            limit < left + right_sums[right_count - 1]
        ) {
            --right_count;
        }
        if (right_count == 0) break;

        const T candidate = left + right_sums[right_count - 1];
        if (answer < candidate) answer = candidate;
    }
    return answer;
}

}  // namespace algo
}  // namespace m1une


#line 12 "algo/sequence/all.hpp"
Back to top page