library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/sparse_table.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "datastructure/plus_minus_one_rmq.hpp"
#include "datastructure/sparse_table.hpp"
#include "algebra/monoid_argmin.hpp"
#include "algebra/monoid_gcd.hpp"
#include "algebra/monoid_max.hpp"
#include "algebra/monoid_min.hpp"
// band without identity: keep the left operand
struct leftmost {
    using S = int;
    static S op(S a, S) {
        return a;
    }
};
template <class M, class F> void stress(std::mt19937& rng, const F& gen) {
    using S = typename M::S;
    int n = 1 + rng() % 40;
    std::vector<S> a(n);
    for (int i = 0; i < n; i++) a[i] = gen(i);
    sparse_table<M> st(a);
    for (int l = 0; l < n; l++) {
        for (int r = l + 1; r <= n; r++) {
            S expect = a[l];
            for (int i = l + 1; i < r; i++) expect = M::op(expect, a[i]);
            assert(st.prod(l, r) == expect);
        }
    }
}
int main() {
    std::mt19937 rng(99);
    for (int it = 0; it < 300; it++) {
        stress<monoid_min<int>>(rng, [&](int) { return int(rng() % 100); });
        stress<monoid_max<long long>>(rng, [&](int) { return (long long)(rng() % 100) - 50; });
        stress<monoid_gcd<int>>(rng, [&](int) { return int(rng() % 60); });
        stress<leftmost>(rng, [&](int i) { return i * 7 % 13; });
        {
            int n = 1 + rng() % 40;
            std::vector<monoid_argmin<int>::S> a(n);
            std::vector<int> v(n);
            for (int i = 0; i < n; i++) v[i] = rng() % 5, a[i] = {v[i], i};
            sparse_table<monoid_argmin<int>> st(a);
            for (int l = 0; l < n; l++) {
                for (int r = l + 1; r <= n; r++) {
                    int best = l;
                    for (int i = l; i < r; i++) {
                        if (v[i] < v[best]) best = i;
                    }
                    assert(st.prod(l, r).id == best && st.prod(l, r).val == v[best]);
                }
            }
        }
        {
            int n = 1 + rng() % 70;
            std::vector<int> v(n);
            v[0] = rng() % 3;
            for (int i = 1; i < n; i++) v[i] = v[i - 1] + (rng() % 2 ? 1 : -1);
            plus_minus_one_rmq rmq(v);
            for (int l = 0; l < n; l++) {
                for (int r = l + 1; r <= n; r++) {
                    int best = l;
                    for (int i = l; i < r; i++) {
                        if (v[i] < v[best]) best = i;
                    }
                    assert(rmq.prod(l, r) == best);
                }
            }
        }
    }
    std::cout << "Hello World" << std::endl;
}
#line 1 "test/unit/sparse_table.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#line 3 "datastructure/plus_minus_one_rmq.hpp"
#include <bit>
#line 6 "datastructure/plus_minus_one_rmq.hpp"

#line 6 "datastructure/sparse_table.hpp"

#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};
#line 8 "datastructure/sparse_table.hpp"
template <semigroup M> struct sparse_table {
    using S = typename M::S;
    sparse_table() : _n(0) {
    }
    explicit sparse_table(const std::vector<S>& a) : _n(int(a.size())) {
        int log = std::max(1, std::bit_width((unsigned)_n));
        t.resize(log);
        t[0] = a;
        for (int k = 1; k < log; k++) {
            t[k].resize(_n - (1 << k) + 1);
            for (int i = 0; i + (1 << k) <= _n; i++) {
                t[k][i] = M::op(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    S prod(int l, int r) const {
        assert(0 <= l && l < r && r <= _n);
        int k = std::bit_width((unsigned)(r - l)) - 1;
        return M::op(t[k][l], t[k][r - (1 << k)]);
    }

private:
    int _n;
    std::vector<std::vector<S>> t;
};
#line 2 "algebra/monoid_argmin.hpp"
#include <limits>
template <class T>
struct monoid_argmin {
    struct S {
        T val;
        int id;
    };
    static S op(S a, S b) {
        if (a.val != b.val) return a.val < b.val ? a : b;
        return a.id < b.id ? a : b;
    }
    static S e() {
        return {std::numeric_limits<T>::max(), -1};
    }
};
#line 9 "datastructure/plus_minus_one_rmq.hpp"
struct plus_minus_one_rmq {
public:
    plus_minus_one_rmq() : _n(0), s(1), B(0) {
    }
    explicit plus_minus_one_rmq(const std::vector<int>& a) : _n(int(a.size())), v(a) {
        s = std::max(1, (std::bit_width((unsigned)_n) - 1) / 2);
        B = (_n + s - 1) / s;
        std::vector<monoid_argmin<int>::S> blocks(B);
        pattern.resize(B);
        for (int i = 0; i < _n; i += s) {
            int min_j = i;
            int bit = 0;
            int end = std::min(_n, i + s);
            for (int j = i; j < end; j++) {
                if (v[j] < v[min_j]) min_j = j;
                if (j + 1 < end && v[j] < v[j + 1]) bit |= 1 << (j - i);
            }
            blocks[i / s] = {v[min_j], min_j};
            pattern[i / s] = bit;
        }
        table = sparse_table<monoid_argmin<int>>(blocks);
        lookup.resize(1 << (s - 1));
        for (int bit = 0; bit < (1 << (s - 1)); bit++) {
            lookup[bit].resize(s + 1);
            for (int l = 0; l <= s; l++) {
                lookup[bit][l].assign(s + 1, INF);
                int min_sum = 0, min_i = l, sum = 0;
                for (int r = l + 1; r <= s; r++) {
                    lookup[bit][l][r] = min_i;
                    sum += bit >> (r - 1) & 1 ? 1 : -1;
                    if (sum < min_sum) {
                        min_sum = sum;
                        min_i = r;
                    }
                }
            }
        }
    }
    int prod(int l, int r) const {
        assert(0 <= l && l < r && r <= _n);
        int m1 = (l + s - 1) / s, m2 = r / s;
        int l1 = s * m1, r1 = s * m2;
        if (m2 < m1) return lookup[pattern[m2]][l - r1][r - r1] + r1;
        int ret = INF;
        if (m1 > 0) ret = argmin(ret, lookup[pattern[m1 - 1]][s - (l1 - l)][s] + l1 - s);
        if (m1 < m2) ret = argmin(ret, table.prod(m1, m2).id);
        if (m2 < B) ret = argmin(ret, lookup[pattern[m2]][0][r - r1] + r1);
        return ret;
    }

private:
    static constexpr int INF = 1 << 30;
    int _n, s, B;
    std::vector<int> v, pattern;
    sparse_table<monoid_argmin<int>> table;
    std::vector<std::vector<std::vector<int>>> lookup;
    int argmin(int i, int j) const {
        if (i >= INF) return j;
        if (j >= INF) return i;
        if (v[i] != v[j]) return v[i] < v[j] ? i : j;
        return std::min(i, j);
    }
};
#line 3 "algebra/monoid_gcd.hpp"
template <class T>
struct monoid_gcd {
    using S = T;
    static S op(S a, S b) {
        return std::gcd(a, b);
    }
    static S e() {
        return T(0);
    }
};
#line 4 "algebra/monoid_max.hpp"
template <class T>
struct monoid_max {
    using S = T;
    static S op(S a, S b) {
        return std::max(a, b);
    }
    static S e() {
        return std::numeric_limits<T>::lowest();
    }
};
#line 4 "algebra/monoid_min.hpp"
template <class T>
struct monoid_min {
    using S = T;
    static S op(S a, S b) {
        return std::min(a, b);
    }
    static S e() {
        return std::numeric_limits<T>::max();
    }
};
#line 15 "test/unit/sparse_table.test.cpp"
// band without identity: keep the left operand
struct leftmost {
    using S = int;
    static S op(S a, S) {
        return a;
    }
};
template <class M, class F> void stress(std::mt19937& rng, const F& gen) {
    using S = typename M::S;
    int n = 1 + rng() % 40;
    std::vector<S> a(n);
    for (int i = 0; i < n; i++) a[i] = gen(i);
    sparse_table<M> st(a);
    for (int l = 0; l < n; l++) {
        for (int r = l + 1; r <= n; r++) {
            S expect = a[l];
            for (int i = l + 1; i < r; i++) expect = M::op(expect, a[i]);
            assert(st.prod(l, r) == expect);
        }
    }
}
int main() {
    std::mt19937 rng(99);
    for (int it = 0; it < 300; it++) {
        stress<monoid_min<int>>(rng, [&](int) { return int(rng() % 100); });
        stress<monoid_max<long long>>(rng, [&](int) { return (long long)(rng() % 100) - 50; });
        stress<monoid_gcd<int>>(rng, [&](int) { return int(rng() % 60); });
        stress<leftmost>(rng, [&](int i) { return i * 7 % 13; });
        {
            int n = 1 + rng() % 40;
            std::vector<monoid_argmin<int>::S> a(n);
            std::vector<int> v(n);
            for (int i = 0; i < n; i++) v[i] = rng() % 5, a[i] = {v[i], i};
            sparse_table<monoid_argmin<int>> st(a);
            for (int l = 0; l < n; l++) {
                for (int r = l + 1; r <= n; r++) {
                    int best = l;
                    for (int i = l; i < r; i++) {
                        if (v[i] < v[best]) best = i;
                    }
                    assert(st.prod(l, r).id == best && st.prod(l, r).val == v[best]);
                }
            }
        }
        {
            int n = 1 + rng() % 70;
            std::vector<int> v(n);
            v[0] = rng() % 3;
            for (int i = 1; i < n; i++) v[i] = v[i - 1] + (rng() % 2 ? 1 : -1);
            plus_minus_one_rmq rmq(v);
            for (int l = 0; l < n; l++) {
                for (int r = l + 1; r <= n; r++) {
                    int best = l;
                    for (int i = l; i < r; i++) {
                        if (v[i] < v[best]) best = i;
                    }
                    assert(rmq.prod(l, r) == best);
                }
            }
        }
    }
    std::cout << "Hello World" << std::endl;
}
Back to top page