library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/segtree_beats.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 <random>
#include <vector>

#include "algebra/range_chmin_chmax_add_range_sum.hpp"
#include "datastructure/segtree_beats.hpp"
int main() {
    using A = range_chmin_chmax_add_range_sum<long long>;
    std::mt19937 rng(20261029);
    for (int trial = 0; trial < 300; trial++) {
        int n = 1 + rng() % 40;
        std::vector<long long> a(n);
        std::vector<A::S> init(n);
        for (int i = 0; i < n; i++) {
            a[i] = (long long)(rng() % 41) - 20;
            init[i] = A::from(a[i]);
        }
        segtree_beats<A> seg(init);
        for (int step = 0; step < 300; step++) {
            int l = rng() % (n + 1), r = rng() % (n + 1);
            if (l > r) std::swap(l, r);
            long long x = (long long)(rng() % 41) - 20;
            int t = rng() % 9;
            if (t == 0) {
                seg.apply(l, r, A::chmin(x));
                for (int i = l; i < r; i++) a[i] = std::min(a[i], x);
            } else if (t == 1) {
                seg.apply(l, r, A::chmax(x));
                for (int i = l; i < r; i++) a[i] = std::max(a[i], x);
            } else if (t == 2) {
                seg.apply(l, r, A::add(x));
                for (int i = l; i < r; i++) a[i] += x;
            } else if (t == 3) {
                seg.apply(l, r, A::assign(x));
                for (int i = l; i < r; i++) a[i] = x;
            } else if (t == 4) {
                int p = rng() % n;
                seg.set(p, A::from(x));
                a[p] = x;
            } else if (t == 5) {
                int p = rng() % n;
                assert(seg.get(p).sum == a[p]);
            } else if (t == 6) {
                int p = rng() % n;
                seg.apply(p, A::add(x));
                a[p] += x;
            } else if (t == 7) {
                long long lim = a[rng() % n];
                int want = l;
                while (want < n && a[want] <= lim) want++;
                int got = seg.max_right(l, [&](A::S v) { return v.max <= lim; });
                assert(got == want);
                int want_l = r;
                while (want_l > 0 && a[want_l - 1] <= lim) want_l--;
                int got_l = seg.min_left(r, [&](A::S v) { return v.max <= lim; });
                assert(got_l == want_l);
            }
            A::S p = seg.prod(l, r);
            long long sum = 0, mn = std::numeric_limits<long long>::max(), mx = std::numeric_limits<long long>::lowest();
            for (int i = l; i < r; i++) {
                sum += a[i];
                mn = std::min(mn, a[i]);
                mx = std::max(mx, a[i]);
            }
            assert(p.sum == sum && p.min == mn && p.max == mx && !p.fail);
            A::S all = seg.all_prod();
            long long total = 0;
            for (long long v : a) total += v;
            assert(all.sum == total);
        }
    }
    std::cout << "Hello World\n";
}
#line 1 "test/unit/segtree_beats.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#line 3 "algebra/range_chmin_chmax_add_range_sum.hpp"
#include <limits>
template <class T>
struct range_chmin_chmax_add_range_sum {
    struct S {
        T sum, min, max, min2, max2;
        int minc, maxc, len;
        bool fail;
    };
    struct F {
        T add, chmin, chmax;
    };
    static S op(S a, S b) {
        if (a.len == 0) return b;
        if (b.len == 0) return a;
        S c;
        c.sum = a.sum + b.sum;
        c.len = a.len + b.len;
        c.fail = false;
        if (a.max > b.max) {
            c.max = a.max;
            c.maxc = a.maxc;
            c.max2 = std::max(a.max2, b.max);
        } else if (a.max < b.max) {
            c.max = b.max;
            c.maxc = b.maxc;
            c.max2 = std::max(a.max, b.max2);
        } else {
            c.max = a.max;
            c.maxc = a.maxc + b.maxc;
            c.max2 = std::max(a.max2, b.max2);
        }
        if (a.min < b.min) {
            c.min = a.min;
            c.minc = a.minc;
            c.min2 = std::min(a.min2, b.min);
        } else if (a.min > b.min) {
            c.min = b.min;
            c.minc = b.minc;
            c.min2 = std::min(a.min, b.min2);
        } else {
            c.min = a.min;
            c.minc = a.minc + b.minc;
            c.min2 = std::min(a.min2, b.min2);
        }
        return c;
    }
    static S e() {
        return {T(0), inf, ninf, inf, ninf, 0, 0, 0, false};
    }
    static S mapping(F f, S x) {
        if (x.len == 0) return x;
        if (f.add != T(0)) {
            x.sum += f.add * x.len;
            x.min += f.add;
            x.max += f.add;
            if (x.min2 != inf) x.min2 += f.add;
            if (x.max2 != ninf) x.max2 += f.add;
        }
        if (f.chmin < x.max) {
            if (f.chmin <= x.min) {
                fill(x, f.chmin);
            } else if (x.max2 < f.chmin) {
                x.sum += (f.chmin - x.max) * x.maxc;
                if (x.min2 == x.max) x.min2 = f.chmin;
                x.max = f.chmin;
            } else {
                x.fail = true;
                return x;
            }
        }
        if (f.chmax > x.min) {
            if (f.chmax >= x.max) {
                fill(x, f.chmax);
            } else if (f.chmax < x.min2) {
                x.sum += (f.chmax - x.min) * x.minc;
                if (x.max2 == x.min) x.max2 = f.chmax;
                x.min = f.chmax;
            } else {
                x.fail = true;
            }
        }
        return x;
    }
    static F composition(F f, F g) {
        T chmin = g.chmin == inf ? inf : g.chmin + f.add;
        T chmax = g.chmax == ninf ? ninf : g.chmax + f.add;
        return {f.add + g.add, std::min(chmin, f.chmin), std::max(std::min(chmax, f.chmin), f.chmax)};
    }
    static F id() {
        return {T(0), inf, ninf};
    }
    static constexpr bool composition_commutative = false;
    static S from(T v) {
        return {v, v, v, inf, ninf, 1, 1, 1, false};
    }
    static F chmin(T x) {
        return {T(0), x, ninf};
    }
    static F chmax(T x) {
        return {T(0), inf, x};
    }
    static F add(T x) {
        return {x, inf, ninf};
    }
    static F assign(T x) {
        return {T(0), x, x};
    }

private:
    static constexpr T inf = std::numeric_limits<T>::max();
    static constexpr T ninf = std::numeric_limits<T>::lowest();
    static void fill(S& x, T v) {
        x.sum = v * x.len;
        x.min = x.max = v;
        x.min2 = inf;
        x.max2 = ninf;
        x.minc = x.maxc = x.len;
    }
};
#line 2 "datastructure/segtree_beats.hpp"
#include <bit>
#line 5 "datastructure/segtree_beats.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>;
};
template <class A>
concept beats_acted_monoid = acted_monoid<A> && requires(typename A::S x) {
    { x.fail } -> std::convertible_to<bool>;
};
#line 7 "datastructure/segtree_beats.hpp"
template <beats_acted_monoid A> struct segtree_beats {
public:
    using S = typename A::S;
    using F = typename A::F;
    segtree_beats() : segtree_beats(0) {
    }
    explicit segtree_beats(int n) : segtree_beats(std::vector<S>(n, A::e())) {
    }
    explicit segtree_beats(const std::vector<S>& v) : _n(int(v.size())) {
        size = int(std::bit_ceil(unsigned(_n)));
        log = std::countr_zero(unsigned(size));
        d = std::vector<S>(2 * size, A::e());
        lz = std::vector<F>(size, A::id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) update(i);
    }
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return A::e();
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        S sml = A::e(), smr = A::e();
        while (l < r) {
            if (l & 1) sml = A::op(sml, d[l++]);
            if (r & 1) smr = A::op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return A::op(sml, smr);
    }
    S all_prod() const {
        return d[1];
    }
    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = A::mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(A::e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = A::e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(A::op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(A::op(sm, d[l]))) {
                        sm = A::op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = A::op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(A::e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = A::e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(A::op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(A::op(d[r], sm))) {
                        sm = A::op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = A::op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
    void update(int k) {
        d[k] = A::op(d[2 * k], d[2 * k + 1]);
    }
    void all_apply(int k, F f) {
        d[k] = A::mapping(f, d[k]);
        if (k < size) {
            lz[k] = A::composition(f, lz[k]);
            if (d[k].fail) {
                push(k);
                update(k);
            }
        }
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = A::id();
    }
};
#line 10 "test/unit/segtree_beats.test.cpp"
int main() {
    using A = range_chmin_chmax_add_range_sum<long long>;
    std::mt19937 rng(20261029);
    for (int trial = 0; trial < 300; trial++) {
        int n = 1 + rng() % 40;
        std::vector<long long> a(n);
        std::vector<A::S> init(n);
        for (int i = 0; i < n; i++) {
            a[i] = (long long)(rng() % 41) - 20;
            init[i] = A::from(a[i]);
        }
        segtree_beats<A> seg(init);
        for (int step = 0; step < 300; step++) {
            int l = rng() % (n + 1), r = rng() % (n + 1);
            if (l > r) std::swap(l, r);
            long long x = (long long)(rng() % 41) - 20;
            int t = rng() % 9;
            if (t == 0) {
                seg.apply(l, r, A::chmin(x));
                for (int i = l; i < r; i++) a[i] = std::min(a[i], x);
            } else if (t == 1) {
                seg.apply(l, r, A::chmax(x));
                for (int i = l; i < r; i++) a[i] = std::max(a[i], x);
            } else if (t == 2) {
                seg.apply(l, r, A::add(x));
                for (int i = l; i < r; i++) a[i] += x;
            } else if (t == 3) {
                seg.apply(l, r, A::assign(x));
                for (int i = l; i < r; i++) a[i] = x;
            } else if (t == 4) {
                int p = rng() % n;
                seg.set(p, A::from(x));
                a[p] = x;
            } else if (t == 5) {
                int p = rng() % n;
                assert(seg.get(p).sum == a[p]);
            } else if (t == 6) {
                int p = rng() % n;
                seg.apply(p, A::add(x));
                a[p] += x;
            } else if (t == 7) {
                long long lim = a[rng() % n];
                int want = l;
                while (want < n && a[want] <= lim) want++;
                int got = seg.max_right(l, [&](A::S v) { return v.max <= lim; });
                assert(got == want);
                int want_l = r;
                while (want_l > 0 && a[want_l - 1] <= lim) want_l--;
                int got_l = seg.min_left(r, [&](A::S v) { return v.max <= lim; });
                assert(got_l == want_l);
            }
            A::S p = seg.prod(l, r);
            long long sum = 0, mn = std::numeric_limits<long long>::max(), mx = std::numeric_limits<long long>::lowest();
            for (int i = l; i < r; i++) {
                sum += a[i];
                mn = std::min(mn, a[i]);
                mx = std::max(mx, a[i]);
            }
            assert(p.sum == sum && p.min == mn && p.max == mx && !p.fail);
            A::S all = seg.all_prod();
            long long total = 0;
            for (long long v : a) total += v;
            assert(all.sum == total);
        }
    }
    std::cout << "Hello World\n";
}
Back to top page