This documentation is automatically generated by online-judge-tools/verification-helper
#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";
}