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 <chrono>
#include <iostream>
#include <random>
#include <vector>
#include "algebra/monoid_add.hpp"
#include "algebra/monoid_min.hpp"
#include "datastructure/persistent_segtree.hpp"
template <class M, class Naive>
void stress(std::mt19937_64& rng, const Naive& naive) {
using S = typename M::S;
for (int iter = 0; iter < 200; iter++) {
int n = 1 + rng() % 20;
std::vector<S> init(n);
for (auto& x : init) x = S(rng() % 100);
persistent_segtree<M> seg(init);
std::vector<std::vector<S>> versions{init};
std::vector<int> roots{0};
assert(seg.size() == n);
for (int t = 0; t < 60; t++) {
int k = rng() % roots.size();
int p = rng() % n;
S x = S(rng() % 100);
roots.push_back(seg.set(roots[k], p, x));
std::vector<S> v = versions[k];
v[p] = x;
versions.push_back(v);
int c = rng() % roots.size();
for (int i = 0; i < n; i++) assert(seg.get(roots[c], i) == versions[c][i]);
for (int l = 0; l <= n; l++) {
for (int r = l; r <= n; r++) {
S expect = M::e();
for (int i = l; i < r; i++) expect = naive(expect, versions[c][i]);
assert(seg.prod(roots[c], l, r) == expect);
}
}
assert(seg.all_prod(roots[c]) == seg.prod(roots[c], 0, n));
}
}
}
int main() {
std::mt19937_64 rng(20261027);
stress<monoid_add<long long>>(rng, [](long long a, long long b) { return a + b; });
stress<monoid_min<int>>(rng, [](int a, int b) { return std::min(a, b); });
{
persistent_segtree<monoid_add<int>> seg(0);
assert(seg.all_prod(0) == 0 && seg.prod(0, 0, 0) == 0);
persistent_segtree<monoid_add<int>> seg1(3);
int r = seg1.set(0, 1, 5);
assert(seg1.all_prod(0) == 0 && seg1.all_prod(r) == 5 && seg1.prod(r, 1, 2) == 5);
}
{
int n = 200000, q = 200000;
auto start = std::chrono::steady_clock::now();
persistent_segtree<monoid_add<long long>> seg(n);
std::vector<int> roots{0};
long long acc = 0;
for (int i = 0; i < q; i++) {
int k = rng() % roots.size();
roots.push_back(seg.set(roots[k], rng() % n, rng() % 1000));
int l = rng() % n, r = rng() % n;
if (l > r) std::swap(l, r);
acc += seg.prod(roots[rng() % roots.size()], l, r + 1);
}
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
std::cerr << "perf n=q=" << n << ": " << ms << " ms (" << acc % 1000 << ")\n";
}
std::cout << "Hello World\n";
}#line 1 "test/unit/persistent_segtree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#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 3 "algebra/monoid_min.hpp"
#include <limits>
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 4 "datastructure/persistent_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 6 "datastructure/persistent_segtree.hpp"
template <monoid M> struct persistent_segtree {
public:
using S = typename M::S;
explicit persistent_segtree(int n) : persistent_segtree(std::vector<S>(n, M::e())) {
}
explicit persistent_segtree(const std::vector<S>& v) : _n(int(v.size())) {
nodes.reserve(2 * _n);
if (_n > 0) build(v, 0, _n);
}
int size() const {
return _n;
}
S get(int root, int p) const {
assert(0 <= p && p < _n);
int cur = root, l = 0, r = _n;
while (r - l > 1) {
int mid = (l + r) / 2;
if (p < mid) {
cur = nodes[cur].l, r = mid;
} else {
cur = nodes[cur].r, l = mid;
}
}
return nodes[cur].val;
}
int set(int root, int p, const S& x) {
assert(0 <= p && p < _n);
int res = copy(root);
int cur = res, l = 0, r = _n;
path.clear();
while (r - l > 1) {
path.push_back(cur);
int mid = (l + r) / 2;
if (p < mid) {
int nxt = copy(nodes[cur].l);
nodes[cur].l = nxt;
cur = nxt, r = mid;
} else {
int nxt = copy(nodes[cur].r);
nodes[cur].r = nxt;
cur = nxt, l = mid;
}
}
nodes[cur].val = x;
for (int i = int(path.size()) - 1; i >= 0; i--) {
node& v = nodes[path[i]];
v.val = M::op(nodes[v.l].val, nodes[v.r].val);
}
return res;
}
S prod(int root, int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
return prod(root, 0, _n, l, r);
}
S all_prod(int root) const {
return _n == 0 ? M::e() : nodes[root].val;
}
private:
struct node {
int l, r;
S val;
};
int _n;
std::vector<node> nodes;
std::vector<int> path;
int copy(int v) {
nodes.push_back(nodes[v]);
return int(nodes.size()) - 1;
}
int build(const std::vector<S>& v, int l, int r) {
if (r - l == 1) {
nodes.push_back({-1, -1, v[l]});
return int(nodes.size()) - 1;
}
int mid = (l + r) / 2;
int res = int(nodes.size());
nodes.push_back({-1, -1, M::e()});
int lc = build(v, l, mid);
int rc = build(v, mid, r);
nodes[res].l = lc, nodes[res].r = rc;
nodes[res].val = M::op(nodes[lc].val, nodes[rc].val);
return res;
}
S prod(int cur, int nl, int nr, int l, int r) const {
if (r <= nl || nr <= l) return M::e();
if (l <= nl && nr <= r) return nodes[cur].val;
int mid = (nl + nr) / 2;
return M::op(prod(nodes[cur].l, nl, mid, l, r), prod(nodes[cur].r, mid, nr, l, r));
}
};
#line 12 "test/unit/persistent_segtree.test.cpp"
template <class M, class Naive>
void stress(std::mt19937_64& rng, const Naive& naive) {
using S = typename M::S;
for (int iter = 0; iter < 200; iter++) {
int n = 1 + rng() % 20;
std::vector<S> init(n);
for (auto& x : init) x = S(rng() % 100);
persistent_segtree<M> seg(init);
std::vector<std::vector<S>> versions{init};
std::vector<int> roots{0};
assert(seg.size() == n);
for (int t = 0; t < 60; t++) {
int k = rng() % roots.size();
int p = rng() % n;
S x = S(rng() % 100);
roots.push_back(seg.set(roots[k], p, x));
std::vector<S> v = versions[k];
v[p] = x;
versions.push_back(v);
int c = rng() % roots.size();
for (int i = 0; i < n; i++) assert(seg.get(roots[c], i) == versions[c][i]);
for (int l = 0; l <= n; l++) {
for (int r = l; r <= n; r++) {
S expect = M::e();
for (int i = l; i < r; i++) expect = naive(expect, versions[c][i]);
assert(seg.prod(roots[c], l, r) == expect);
}
}
assert(seg.all_prod(roots[c]) == seg.prod(roots[c], 0, n));
}
}
}
int main() {
std::mt19937_64 rng(20261027);
stress<monoid_add<long long>>(rng, [](long long a, long long b) { return a + b; });
stress<monoid_min<int>>(rng, [](int a, int b) { return std::min(a, b); });
{
persistent_segtree<monoid_add<int>> seg(0);
assert(seg.all_prod(0) == 0 && seg.prod(0, 0, 0) == 0);
persistent_segtree<monoid_add<int>> seg1(3);
int r = seg1.set(0, 1, 5);
assert(seg1.all_prod(0) == 0 && seg1.all_prod(r) == 5 && seg1.prod(r, 1, 2) == 5);
}
{
int n = 200000, q = 200000;
auto start = std::chrono::steady_clock::now();
persistent_segtree<monoid_add<long long>> seg(n);
std::vector<int> roots{0};
long long acc = 0;
for (int i = 0; i < q; i++) {
int k = rng() % roots.size();
roots.push_back(seg.set(roots[k], rng() % n, rng() % 1000));
int l = rng() % n, r = rng() % n;
if (l > r) std::swap(l, r);
acc += seg.prod(roots[rng() % roots.size()], l, r + 1);
}
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
std::cerr << "perf n=q=" << n << ": " << ms << " ms (" << acc % 1000 << ")\n";
}
std::cout << "Hello World\n";
}