library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/sqrt_tree.test.cpp

Depends on

Code

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

#include "algebra/monoid_add.hpp"
#include "datastructure/sqrt_tree.hpp"

// non-commutative, non-idempotent: composition of x -> a x + b mod 1e9+7
struct affine {
    using S = std::pair<long long, long long>;
    static constexpr long long mod = 1000000007;
    static S op(S f, S g) {  // g after f
        return {g.first * f.first % mod, (g.first * f.second + g.second) % mod};
    }
};

int main() {
    std::mt19937 rng(31);
    for (int it = 0; it < 200; it++) {
        int n = 1 + rng() % 70;
        std::vector<long long> a(n);
        for (auto& x : a) x = rng() % 1000;
        std::vector<affine::S> f(n);
        for (auto& [p, q] : f) p = 1 + rng() % 1000, q = rng() % 1000;
        sqrt_tree<monoid_add<long long>> sa(a);
        sqrt_tree<affine> sf(f);
        for (int l = 0; l < n; l++) {
            long long sum = 0;
            affine::S comp = {1, 0};
            for (int r = l + 1; r <= n; r++) {
                sum += a[r - 1];
                comp = affine::op(comp, f[r - 1]);
                assert(sa.prod(l, r) == sum);
                assert(sf.prod(l, r) == comp);
            }
        }
    }
    {
        int n = 500000;
        std::vector<long long> a(n);
        for (auto& x : a) x = rng() % 1000;
        sqrt_tree<monoid_add<long long>> s(a);
        assert(s.prod(0, n) == std::accumulate(a.begin(), a.end(), 0LL));
    }
    std::cout << "Hello World" << std::endl;
}
#line 1 "test/unit/sqrt_tree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <random>
#include <numeric>
#include <utility>
#include <vector>

#line 2 "algebra/monoid_add.hpp"
template <class T>
struct monoid_add {
    using S = T;
    static S op(S a, S b) {
        return a + b;
    }
    static S e() {
        return T(0);
    }
};
#line 2 "datastructure/sqrt_tree.hpp"
#include <algorithm>
#line 5 "datastructure/sqrt_tree.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 7 "datastructure/sqrt_tree.hpp"
template <semigroup M> struct sqrt_tree {
    using S = typename M::S;
    sqrt_tree() {
    }
    explicit sqrt_tree(const std::vector<S>& a) : _n(int(a.size())) {
        if (_n == 0) return;
        _lg = 0;
        while ((1 << _lg) < _n) _lg++;
        v = a;

        clz.assign(1 << _lg, 0);
        for (int i = 1; i < (1 << _lg); i++) {
            clz[i] = clz[i >> 1] + 1;
        }

        on_layer.assign(_lg + 1, 0);
        int tlg = _lg;
        while (tlg > 1) {
            on_layer[tlg] = int(layers.size());
            layers.push_back(tlg);
            tlg = (tlg + 1) >> 1;
        }
        for (int i = _lg - 1; i >= 0; i--) {
            on_layer[i] = std::max(on_layer[i], on_layer[i + 1]);
        }

        if (layers.empty()) return;

        int between_layers = std::max(0, int(layers.size()) - 1);
        int b_sz_log = (_lg + 1) >> 1;
        int b_sz = 1 << b_sz_log;
        index_sz = (_n + b_sz - 1) >> b_sz_log;
        v.resize(_n + index_sz);
        pref.assign(layers.size(), std::vector<S>(_n + index_sz));
        suf.assign(layers.size(), std::vector<S>(_n + index_sz));
        between.assign(between_layers, std::vector<S>((1 << _lg) + b_sz));
        build(0, 0, _n, 0);
    }

    S prod(int l, int r) const {
        assert(0 <= l && l < r && r <= _n);
        return query(l, r - 1, 0, 0);
    }

  private:
    int _n = 0, _lg = 0, index_sz = 0;
    std::vector<S> v;
    std::vector<int> clz, layers, on_layer;
    std::vector<std::vector<S>> pref, suf, between;

    void build_block(int layer, int l, int r) {
        pref[layer][l] = v[l];
        for (int i = l + 1; i < r; i++) {
            pref[layer][i] = M::op(pref[layer][i - 1], v[i]);
        }
        suf[layer][r - 1] = v[r - 1];
        for (int i = r - 2; i >= l; i--) {
            suf[layer][i] = M::op(v[i], suf[layer][i + 1]);
        }
    }

    void build_between(int layer, int l_bound, int r_bound, int between_offs) {
        int b_sz_log = (layers[layer] + 1) >> 1;
        int b_cnt_log = layers[layer] >> 1;
        int b_sz = 1 << b_sz_log;
        int b_cnt = (r_bound - l_bound + b_sz - 1) >> b_sz_log;
        for (int i = 0; i < b_cnt; i++) {
            S ans = suf[layer][l_bound + (i << b_sz_log)];
            between[layer - 1][between_offs + l_bound + (i << b_cnt_log) + i] = ans;
            for (int j = i + 1; j < b_cnt; j++) {
                S add = suf[layer][l_bound + (j << b_sz_log)];
                ans = M::op(ans, add);
                between[layer - 1][between_offs + l_bound + (i << b_cnt_log) + j] = ans;
            }
        }
    }

    void build_between_zero() {
        int b_sz_log = (_lg + 1) >> 1;
        for (int i = 0; i < index_sz; i++) {
            v[_n + i] = suf[0][i << b_sz_log];
        }
        build(1, _n, _n + index_sz, (1 << _lg) - _n);
    }

    void build(int layer, int l_bound, int r_bound, int between_offs) {
        if (layer >= int(layers.size())) return;
        int b_sz = 1 << ((layers[layer] + 1) >> 1);
        for (int l = l_bound; l < r_bound; l += b_sz) {
            int r = std::min(l + b_sz, r_bound);
            build_block(layer, l, r);
            build(layer + 1, l, r, between_offs);
        }
        if (layer == 0) {
            build_between_zero();
        } else {
            build_between(layer, l_bound, r_bound, between_offs);
        }
    }

    S query(int l, int r, int between_offs, int base) const {
        if (l == r) return v[l];
        if (l + 1 == r) return M::op(v[l], v[r]);
        int layer = on_layer[clz[(l - base) ^ (r - base)]];
        int b_sz_log = (layers[layer] + 1) >> 1;
        int b_cnt_log = layers[layer] >> 1;
        int l_bound = (((l - base) >> layers[layer]) << layers[layer]) + base;
        int l_block = ((l - l_bound) >> b_sz_log) + 1;
        int r_block = ((r - l_bound) >> b_sz_log) - 1;
        S ans = suf[layer][l];
        if (l_block <= r_block) {
            S add = (layer == 0)
                        ? query(_n + l_block, _n + r_block, (1 << _lg) - _n, _n)
                        : between[layer - 1][between_offs + l_bound + (l_block << b_cnt_log) + r_block];
            ans = M::op(ans, add);
        }
        ans = M::op(ans, pref[layer][r]);
        return ans;
    }
};
#line 11 "test/unit/sqrt_tree.test.cpp"

// non-commutative, non-idempotent: composition of x -> a x + b mod 1e9+7
struct affine {
    using S = std::pair<long long, long long>;
    static constexpr long long mod = 1000000007;
    static S op(S f, S g) {  // g after f
        return {g.first * f.first % mod, (g.first * f.second + g.second) % mod};
    }
};

int main() {
    std::mt19937 rng(31);
    for (int it = 0; it < 200; it++) {
        int n = 1 + rng() % 70;
        std::vector<long long> a(n);
        for (auto& x : a) x = rng() % 1000;
        std::vector<affine::S> f(n);
        for (auto& [p, q] : f) p = 1 + rng() % 1000, q = rng() % 1000;
        sqrt_tree<monoid_add<long long>> sa(a);
        sqrt_tree<affine> sf(f);
        for (int l = 0; l < n; l++) {
            long long sum = 0;
            affine::S comp = {1, 0};
            for (int r = l + 1; r <= n; r++) {
                sum += a[r - 1];
                comp = affine::op(comp, f[r - 1]);
                assert(sa.prod(l, r) == sum);
                assert(sf.prod(l, r) == comp);
            }
        }
    }
    {
        int n = 500000;
        std::vector<long long> a(n);
        for (auto& x : a) x = rng() % 1000;
        sqrt_tree<monoid_add<long long>> s(a);
        assert(s.prod(0, n) == std::accumulate(a.begin(), a.end(), 0LL));
    }
    std::cout << "Hello World" << std::endl;
}
Back to top page