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 <cassert>
#include <iostream>
#include <map>
#include <random>
#include <vector>
#include "algebra/monoid_add.hpp"
#include "algebra/monoid_affine.hpp"
#include "algebra/monoid_max.hpp"
#include "datastructure/dynamic_segtree.hpp"
bool at_most_10(long long x) {
return x <= 10;
}
void stress_small(std::mt19937& rng) {
const long long lo = -(long long)(rng() % 20), hi = lo + 1 + rng() % 40;
const long long n = hi - lo;
std::vector<long long> a(n, 0);
dynamic_segtree<monoid_add<long long>> seg(lo, hi);
for (int it = 0; it < 300; it++) {
int type = rng() % 5;
if (type == 0) {
long long p = lo + rng() % n;
long long x = rng() % 5;
a[p - lo] = x;
seg.set(p, x);
} else if (type == 1) {
long long p = lo + rng() % n;
assert(seg.get(p) == a[p - lo]);
} else if (type == 2) {
long long l = lo + rng() % (n + 1), r = lo + rng() % (n + 1);
if (l > r) std::swap(l, r);
long long expect = 0;
for (long long i = l; i < r; i++) expect += a[i - lo];
assert(seg.prod(l, r) == expect);
} else if (type == 3) {
long long l = lo + rng() % (n + 1);
long long k = rng() % 15;
long long r = l, sum = 0;
while (r < hi && sum + a[r - lo] <= k) sum += a[r - lo], r++;
assert(seg.max_right(l, [&](long long x) { return x <= k; }) == r);
if (k == 10) assert(seg.max_right<at_most_10>(l) == r);
} else {
long long r = lo + rng() % (n + 1);
long long k = rng() % 15;
long long l = r, sum = 0;
while (l > lo && sum + a[l - 1 - lo] <= k) sum += a[l - 1 - lo], l--;
assert(seg.min_left(r, [&](long long x) { return x <= k; }) == l);
}
}
long long total = 0;
for (long long x : a) total += x;
assert(seg.all_prod() == total);
}
void stress_wide(std::mt19937& rng) {
dynamic_segtree<monoid_max<long long>> seg;
std::map<long long, long long> a;
const long long lim = 1LL << 62;
for (int it = 0; it < 300; it++) {
long long p = (long long)(rng() % (2 * (unsigned long long)lim)) - lim;
if (rng() % 2) p = (long long)(rng() % 100) - 50;
if (rng() % 2) {
long long x = rng() % 1000;
a[p] = x;
seg.set(p, x);
} else {
long long q = (long long)(rng() % (2 * (unsigned long long)lim)) - lim;
long long l = std::min(p, q), r = std::max(p, q) + 1;
long long expect = monoid_max<long long>::e();
for (auto it2 = a.lower_bound(l); it2 != a.end() && it2->first < r; ++it2) expect = std::max(expect, it2->second);
assert(seg.prod(l, r) == expect);
}
}
}
void stress_noncommutative(std::mt19937& rng) {
using M = monoid_affine<long long>;
const long long n = 1 + rng() % 30;
std::vector<M::S> a(n, M::e());
dynamic_segtree<M> seg(0, n);
for (int it = 0; it < 200; it++) {
if (rng() % 2) {
long long p = rng() % n;
a[p] = {(long long)(rng() % 3), (long long)(rng() % 3)};
seg.set(p, a[p]);
} else {
long long l = rng() % (n + 1), r = rng() % (n + 1);
if (l > r) std::swap(l, r);
M::S expect = M::e();
for (long long i = l; i < r; i++) expect = M::op(expect, a[i]);
M::S got = seg.prod(l, r);
assert(M::eval(got, 7) == M::eval(expect, 7));
}
}
}
int main() {
std::mt19937 rng(20261028);
for (int trial = 0; trial < 100; trial++) {
stress_small(rng);
stress_wide(rng);
stress_noncommutative(rng);
}
std::cout << "Hello World" << std::endl;
return 0;
}#line 1 "test/unit/dynamic_segtree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <map>
#include <random>
#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 "algebra/monoid_affine.hpp"
template <class T>
struct monoid_affine {
struct S {
T a, b;
};
static S op(S f, S g) {
return {g.a * f.a, g.a * f.b + g.b};
}
static S e() {
return {T(1), T(0)};
}
static T eval(S f, T x) {
return f.a * x + f.b;
}
};
#line 2 "algebra/monoid_max.hpp"
#include <algorithm>
#include <limits>
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 3 "datastructure/dynamic_segtree.hpp"
#include <utility>
#line 5 "datastructure/dynamic_segtree.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/dynamic_segtree.hpp"
template <monoid M> struct dynamic_segtree {
public:
using S = typename M::S;
explicit dynamic_segtree(long long lo = -(1LL << 62), long long hi = 1LL << 62) : lo(lo), hi(hi) {
assert(lo < hi);
}
void set(long long p, S x) {
assert(lo <= p && p < hi);
root = set(root, lo, hi, p, x);
}
S get(long long p) const {
assert(lo <= p && p < hi);
int t = root;
long long a = lo, b = hi;
while (t != -1) {
if (nodes[t].idx == p) return nodes[t].val;
long long c = mid(a, b);
if (p < c) {
t = nodes[t].l, b = c;
} else {
t = nodes[t].r, a = c;
}
}
return M::e();
}
S prod(long long l, long long r) const {
assert(lo <= l && l <= r && r <= hi);
return prod(root, lo, hi, l, r);
}
S all_prod() const {
return root == -1 ? M::e() : nodes[root].prod;
}
template <bool (*f)(S)> long long max_right(long long l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> long long max_right(long long l, F f) const {
assert(lo <= l && l <= hi);
S product = M::e();
assert(f(product));
return max_right(root, lo, hi, l, f, product);
}
template <bool (*f)(S)> long long min_left(long long r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> long long min_left(long long r, F f) const {
assert(lo <= r && r <= hi);
S product = M::e();
assert(f(product));
return min_left(root, lo, hi, r, f, product);
}
private:
struct node {
long long idx;
S val, prod;
int l = -1, r = -1;
};
long long lo, hi;
int root = -1;
std::vector<node> nodes;
static long long mid(long long a, long long b) {
return a + (long long)(((unsigned long long)b - (unsigned long long)a) / 2);
}
void update(int t) {
node& v = nodes[t];
S res = v.l == -1 ? v.val : M::op(nodes[v.l].prod, v.val);
v.prod = v.r == -1 ? res : M::op(res, nodes[v.r].prod);
}
int set(int t, long long a, long long b, long long p, S x) {
if (t == -1) {
nodes.push_back({p, x, x});
return int(nodes.size()) - 1;
}
if (nodes[t].idx == p) {
nodes[t].val = x;
update(t);
return t;
}
long long c = mid(a, b);
if (p < c) {
if (nodes[t].idx < p) std::swap(nodes[t].idx, p), std::swap(nodes[t].val, x);
int child = set(nodes[t].l, a, c, p, x);
nodes[t].l = child;
} else {
if (p < nodes[t].idx) std::swap(nodes[t].idx, p), std::swap(nodes[t].val, x);
int child = set(nodes[t].r, c, b, p, x);
nodes[t].r = child;
}
update(t);
return t;
}
S prod(int t, long long a, long long b, long long l, long long r) const {
if (t == -1 || b <= l || r <= a) return M::e();
const node& v = nodes[t];
if (l <= a && b <= r) return v.prod;
long long c = mid(a, b);
S res = prod(v.l, a, c, l, r);
if (l <= v.idx && v.idx < r) res = M::op(res, v.val);
return M::op(res, prod(v.r, c, b, l, r));
}
template <class F>
long long max_right(int t, long long a, long long b, long long l, const F& f, S& product) const {
if (t == -1 || b <= l) return hi;
const node& v = nodes[t];
if (l <= a && f(M::op(product, v.prod))) {
product = M::op(product, v.prod);
return hi;
}
long long c = mid(a, b);
long long res = max_right(v.l, a, c, l, f, product);
if (res != hi) return res;
if (l <= v.idx) {
product = M::op(product, v.val);
if (!f(product)) return v.idx;
}
return max_right(v.r, c, b, l, f, product);
}
template <class F>
long long min_left(int t, long long a, long long b, long long r, const F& f, S& product) const {
if (t == -1 || r <= a) return lo;
const node& v = nodes[t];
if (b <= r && f(M::op(v.prod, product))) {
product = M::op(v.prod, product);
return lo;
}
long long c = mid(a, b);
long long res = min_left(v.r, c, b, r, f, product);
if (res != lo) return res;
if (v.idx < r) {
product = M::op(v.val, product);
if (!f(product)) return v.idx + 1;
}
return min_left(v.l, a, c, r, f, product);
}
};
#line 12 "test/unit/dynamic_segtree.test.cpp"
bool at_most_10(long long x) {
return x <= 10;
}
void stress_small(std::mt19937& rng) {
const long long lo = -(long long)(rng() % 20), hi = lo + 1 + rng() % 40;
const long long n = hi - lo;
std::vector<long long> a(n, 0);
dynamic_segtree<monoid_add<long long>> seg(lo, hi);
for (int it = 0; it < 300; it++) {
int type = rng() % 5;
if (type == 0) {
long long p = lo + rng() % n;
long long x = rng() % 5;
a[p - lo] = x;
seg.set(p, x);
} else if (type == 1) {
long long p = lo + rng() % n;
assert(seg.get(p) == a[p - lo]);
} else if (type == 2) {
long long l = lo + rng() % (n + 1), r = lo + rng() % (n + 1);
if (l > r) std::swap(l, r);
long long expect = 0;
for (long long i = l; i < r; i++) expect += a[i - lo];
assert(seg.prod(l, r) == expect);
} else if (type == 3) {
long long l = lo + rng() % (n + 1);
long long k = rng() % 15;
long long r = l, sum = 0;
while (r < hi && sum + a[r - lo] <= k) sum += a[r - lo], r++;
assert(seg.max_right(l, [&](long long x) { return x <= k; }) == r);
if (k == 10) assert(seg.max_right<at_most_10>(l) == r);
} else {
long long r = lo + rng() % (n + 1);
long long k = rng() % 15;
long long l = r, sum = 0;
while (l > lo && sum + a[l - 1 - lo] <= k) sum += a[l - 1 - lo], l--;
assert(seg.min_left(r, [&](long long x) { return x <= k; }) == l);
}
}
long long total = 0;
for (long long x : a) total += x;
assert(seg.all_prod() == total);
}
void stress_wide(std::mt19937& rng) {
dynamic_segtree<monoid_max<long long>> seg;
std::map<long long, long long> a;
const long long lim = 1LL << 62;
for (int it = 0; it < 300; it++) {
long long p = (long long)(rng() % (2 * (unsigned long long)lim)) - lim;
if (rng() % 2) p = (long long)(rng() % 100) - 50;
if (rng() % 2) {
long long x = rng() % 1000;
a[p] = x;
seg.set(p, x);
} else {
long long q = (long long)(rng() % (2 * (unsigned long long)lim)) - lim;
long long l = std::min(p, q), r = std::max(p, q) + 1;
long long expect = monoid_max<long long>::e();
for (auto it2 = a.lower_bound(l); it2 != a.end() && it2->first < r; ++it2) expect = std::max(expect, it2->second);
assert(seg.prod(l, r) == expect);
}
}
}
void stress_noncommutative(std::mt19937& rng) {
using M = monoid_affine<long long>;
const long long n = 1 + rng() % 30;
std::vector<M::S> a(n, M::e());
dynamic_segtree<M> seg(0, n);
for (int it = 0; it < 200; it++) {
if (rng() % 2) {
long long p = rng() % n;
a[p] = {(long long)(rng() % 3), (long long)(rng() % 3)};
seg.set(p, a[p]);
} else {
long long l = rng() % (n + 1), r = rng() % (n + 1);
if (l > r) std::swap(l, r);
M::S expect = M::e();
for (long long i = l; i < r; i++) expect = M::op(expect, a[i]);
M::S got = seg.prod(l, r);
assert(M::eval(got, 7) == M::eval(expect, 7));
}
}
}
int main() {
std::mt19937 rng(20261028);
for (int trial = 0; trial < 100; trial++) {
stress_small(rng);
stress_wide(rng);
stress_noncommutative(rng);
}
std::cout << "Hello World" << std::endl;
return 0;
}