This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/data_structure/disjoint_sparse_table.hpp"
int op(int a, int b) {
return min(a, b);
}
int e() {
return (int)1e9;
}
int main() {
DisjointSparseTable<int, op, e> dst(vector<int>{});
assert(dst.prod(0, 0) == e());
DisjointSparseTable<int, op, e> dst2(vector<int>{5, 2, 7});
assert(dst2.prod(0, 0) == e());
assert(dst2.prod(0, 3) == 2);
assert(dst2.prod(2, 3) == 7);
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}#line 1 "verify/unit_test/data_structure/disjoint_sparse_table.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
SetupIO() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(30);
}
} setup_io;
#line 3 "src/data_structure/disjoint_sparse_table.hpp"
template <typename S, auto op, auto e>
struct DisjointSparseTable {
DisjointSparseTable(const vector<S>& v)
: n((int)v.size()), internal_n(n + 2) {
const int b = 32 - __builtin_clz(internal_n - 1);
table.assign(b, vector<S>(internal_n, e()));
for(int k = 1; k < b; ++k) {
const int w = (1 << k);
for(int i = w; i < internal_n; i += w * 2) {
for(int j = i - 1; j > i - w; --j) {
table[k][j - 1] = op(table[k][j], v[j - 1]);
}
const int m = min(i + w - 1, internal_n - 1);
for(int j = i; j < m; ++j) {
table[k][j + 1] = op(table[k][j], v[j - 1]);
}
}
}
}
S prod(const int l, int r) const {
assert(0 <= l and l <= r and r <= n);
++r;
const auto& s = table[31 - __builtin_clz(l xor r)];
return op(s[l], s[r]);
}
private:
int n, internal_n;
vector<vector<S>> table;
};
#line 4 "verify/unit_test/data_structure/disjoint_sparse_table.test.cpp"
int op(int a, int b) {
return min(a, b);
}
int e() {
return (int)1e9;
}
int main() {
DisjointSparseTable<int, op, e> dst(vector<int>{});
assert(dst.prod(0, 0) == e());
DisjointSparseTable<int, op, e> dst2(vector<int>{5, 2, 7});
assert(dst2.prod(0, 0) == e());
assert(dst2.prod(0, 3) == 2);
assert(dst2.prod(2, 3) == 7);
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}