test/sparse_table.test.cpp

View this file on GitHub
Last update: 2022-01-28 13:07:07+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include "../container/sparse_table.cpp"
#include <iostream>
#include <numeric>
#include "../traits/lambda_semigroup.cpp"
#include "../traits/optional_monoid.cpp"
#include "../utility/int_alias.cpp"
#include "../utility/rep.cpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<u32> A(N);
    for (auto& x : A) {
        std::cin >> x;
    }
    const auto sg_instance = lambda_semigroup([&](const int i, const int j) { return A[i] < A[j] ? i : j; });
    std::vector<std::optional<int>> vec(N);
    for (const auto i : rep(0, N)) {
        vec[i] = i;
    }
    SparseTable<OptionalMonoid<decltype(sg_instance)>> table(vec);
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << A[*table.fold(l, r)] << '\n';
    }
    return 0;
}

#line 1 "test/sparse_table.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 2 "container/sparse_table.cpp"
#include <cassert>
#include <vector>
#line 2 "internal/enable_avx2.cpp"

#ifdef ENABLE_AVX2
#define TARGET_AVX2 __attribute__((target("avx2")))
#else
#define TARGET_AVX2
#endif
#line 2 "utility/int_alias.cpp"
#include <cstdint>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 4 "utility/countl_zero.cpp"

TARGET_AVX2 constexpr int countl_zero(u64 x) {
#ifdef __GNUC__
    return x == 0 ? 64 : __builtin_clzll(x);
#else
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return 64 - countr_zero(~x);
#endif
}
#line 4 "utility/bit_width.cpp"

TARGET_AVX2 constexpr int bit_width(const u64 x) { return 64 - countl_zero(x); }
#line 2 "utility/rep.cpp"
#include <algorithm>

class Range {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }
#line 6 "container/sparse_table.cpp"

template <class M> class SparseTable {
    using T = typename M::Type;
    std::vector<std::vector<T>> table;

  public:
    SparseTable() : SparseTable(std::vector<T>()) {}
    explicit SparseTable(const std::vector<T>& vec) {
        const int size = vec.size();
        const int height = bit_width(size);
        table.reserve(height);
        table.push_back(vec);
        for (const int d : rep(1, height)) {
            table.push_back(std::vector<T>(size - (1 << d) + 1, M::identity()));
            for (const int i : rep(table[d].size())) {
                table[d][i] = M::operation(table[d - 1][i], table[d - 1][i + (1 << (d - 1))]);
            }
        }
    }

    int size() const { return table[0].size(); }

    T fold(const int l, const int r) const {
        assert(0 <= l and l <= r and r <= size());
        if (l == r) return M::identity();
        const int d = bit_width(r - l) - 1;
        return M::operation(table[d][l], table[d][r - (1 << d)]);
    }
};
#line 3 "test/sparse_table.test.cpp"
#include <iostream>
#include <numeric>
#line 2 "traits/lambda_semigroup.cpp"
#include <memory>
#include <utility>

template <class F> class LambdaSemiGroup {
    template <class> struct GetArg;
    template <class C, class T> struct GetArg<T (C::*)(T, T) const> { using Type = T; };

    static inline std::unique_ptr<F> OP;

  public:
    using Type = typename GetArg<decltype(&F::operator())>::Type;
    static constexpr Type operation(const Type& l, const Type& r) {
        assert(OP);
        return OP->operator()(l, r);
    }
    explicit constexpr LambdaSemiGroup(F&& f) { OP = std::make_unique<F>(std::forward<F>(f)); }
};

template <class F> decltype(auto) lambda_semigroup(F&& f) { return LambdaSemiGroup<F>(std::forward<F>(f)); }
#line 2 "traits/optional_monoid.cpp"
#include <optional>
#line 4 "traits/optional_monoid.cpp"

template <class S> struct OptionalMonoid {
    using Type = std::optional<typename S::Type>;
    static constexpr Type identity() { return std::nullopt; }
    static constexpr Type operation(const Type& l, const Type& r) {
        if (!l) return r;
        if (!r) return l;
        return Type(std::in_place, S::operation(*l, *r));
    }
};
#line 9 "test/sparse_table.test.cpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<u32> A(N);
    for (auto& x : A) {
        std::cin >> x;
    }
    const auto sg_instance = lambda_semigroup([&](const int i, const int j) { return A[i] < A[j] ? i : j; });
    std::vector<std::optional<int>> vec(N);
    for (const auto i : rep(0, N)) {
        vec[i] = i;
    }
    SparseTable<OptionalMonoid<decltype(sg_instance)>> table(vec);
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        std::cout << A[*table.fold(l, r)] << '\n';
    }
    return 0;
}