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/wavelet_matrix.hpp"
int main() {
{
WaveletMatrix<int> wm(vector<int>{});
assert(wm.range_freq(0, 0, -1) == 0);
assert(wm.range_freq(0, 0, 0) == 0);
assert(wm.range_freq(0, 0, 10) == 0);
assert(wm.prev_value(0, 0, 10) == -1);
assert(wm.next_value(0, 0, 0) == -1);
}
{
WaveletMatrix<int> wm(5);
for(int i = 0; i < 5; ++i) wm.set(i, i * i % 7);
wm.build();
assert(wm.get(0) == 0);
assert(wm.get(1) == 1);
assert(wm.get(2) == 4);
assert(wm.get(3) == 2);
assert(wm.get(4) == 2);
}
mt19937 mt(0);
for(int n = 0; n <= 80; ++n) {
vector<int> a(n);
for(int& x : a) x = mt() % 32;
WaveletMatrix<int> wm(a);
for(int l = 0; l <= n; ++l) {
for(int r = l; r <= n; ++r) {
vector<int> b(a.begin() + l, a.begin() + r);
sort(b.begin(), b.end());
for(int upper = -2; upper <= 35; ++upper) {
const int freq = lower_bound(b.begin(), b.end(), upper) - b.begin();
assert(wm.range_freq(l, r, upper) == freq);
if(upper >= 0) assert(wm.range_freq(l, r, 0, upper) == freq);
const int less = lower_bound(b.begin(), b.end(), upper) - b.begin();
assert(wm.prev_value(l, r, upper) == (less == 0 ? -1 : b[less - 1]));
assert(wm.next_value(l, r, upper) == (less == (int)b.size() ? -1 : b[less]));
}
for(int k = 0; k < (int)b.size(); ++k) {
assert(wm.kth_smallest(l, r, k) == b[k]);
assert(wm.kth_largest(l, r, k) == b[(int)b.size() - 1 - k]);
}
}
}
}
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}#line 1 "verify/unit_test/data_structure/wavelet_matrix.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/bit_vector.hpp"
#if __has_include(<immintrin.h>)
#include <immintrin.h>
#define CP_LIBRARY_TARGET_POPCNT __attribute__((target("popcnt")))
#define CP_LIBRARY_TARGET_BMI __attribute__((target("bmi")))
#define CP_LIBRARY_TARGET_BMI2_POPCNT __attribute__((target("bmi2,popcnt")))
#else
#define CP_LIBRARY_TARGET_POPCNT
#define CP_LIBRARY_TARGET_BMI
#define CP_LIBRARY_TARGET_BMI2_POPCNT
#endif
CP_LIBRARY_TARGET_POPCNT inline uint32_t popcount64(const uint64_t x) {
#if __has_include(<immintrin.h>)
return _mm_popcnt_u64(x);
#else
return __builtin_popcountll(x);
#endif
}
CP_LIBRARY_TARGET_BMI2_POPCNT inline uint64_t low_bits(const uint64_t x, const uint32_t n) {
#if __has_include(<immintrin.h>)
return _bzhi_u64(x, n);
#else
return n == 64 ? x : x & ((uint64_t(1) << n) - 1);
#endif
}
CP_LIBRARY_TARGET_BMI inline uint32_t lowbit(const uint32_t x) {
#if __has_include(<immintrin.h>)
return _blsi_u32(x);
#else
return x & -x;
#endif
}
CP_LIBRARY_TARGET_BMI inline uint32_t clear_lowbit(const uint32_t x) {
#if __has_include(<immintrin.h>)
return _blsr_u32(x);
#else
return x & (x - 1);
#endif
}
struct BitVector {
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
static constexpr u32 w = 64;
vector<u64> block;
vector<u32> count;
u32 n, zeros;
inline u32 get(const u32 i) const {
return u32(block[i / w] >> (i % w)) & 1u;
}
inline void set(const u32 i) {
block[i / w] |= 1ULL << (i % w);
}
BitVector() {}
BitVector(const int _n) {
init(_n);
}
__attribute__((optimize("O3,unroll-loops"))) void init(const int _n) {
n = zeros = _n;
block.assign(n / w + 1, 0);
count.assign(block.size(), 0);
}
CP_LIBRARY_TARGET_POPCNT void build() {
for(u32 i = 1; i < block.size(); ++i) {
count[i] = count[i - 1] + popcount64(block[i - 1]);
}
zeros = rank0(n);
}
inline u32 rank0(const u32 i) const {
return i - rank1(i);
}
CP_LIBRARY_TARGET_BMI2_POPCNT inline u32 rank1(const u32 i) const {
return count[i / w] + popcount64(low_bits(block[i / w], i % w));
}
};
#line 4 "src/data_structure/wavelet_matrix.hpp"
template <typename T>
struct WaveletMatrix {
private:
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
int n, lg;
vector<T> a;
vector<BitVector> bv;
inline pair<u32, u32> succ0(const int l, const int r, const int h) const {
return make_pair(bv[h].rank0(l), bv[h].rank0(r));
}
inline pair<u32, u32> succ1(const int l, const int r, const int h) const {
const u32 l0 = bv[h].rank0(l);
const u32 r0 = bv[h].rank0(r);
const u32 zeros = bv[h].zeros;
return make_pair(l + zeros - l0, r + zeros - r0);
}
public:
WaveletMatrix(const u32 _n)
: n(_n), lg(0), a(n) {}
WaveletMatrix(const vector<T>& _a)
: n(_a.size()), lg(0), a(_a) {
build();
}
__attribute__((optimize("O3"))) void build() {
if(n == 0) {
lg = 0;
bv.clear();
return;
}
for(const T& x : a) assert(x >= 0);
lg = __lg(max<T>(*max_element(begin(a), end(a)), 1)) + 1;
bv.assign(lg, n);
vector<T> cur = a, nxt(n);
for(int h = lg - 1; h >= 0; --h) {
for(int i = 0; i < n; ++i)
if((cur[i] >> h) & 1) bv[h].set(i);
bv[h].build();
array<decltype(begin(nxt)), 2> it{begin(nxt), begin(nxt) + bv[h].zeros};
for(int i = 0; i < n; ++i) *it[bv[h].get(i)]++ = cur[i];
swap(cur, nxt);
}
return;
}
void set(const int i, const T& x) {
assert(0 <= i and i < n);
assert(x >= 0);
a[i] = x;
}
T get(u32 k) const {
assert(int(k) < n);
T ret = 0;
for(int h = lg - 1; h >= 0; --h) {
const u32 f = bv[h].get(k);
ret |= f ? T(1) << h : 0;
k = f ? bv[h].rank1(k) + bv[h].zeros : bv[h].rank0(k);
}
return ret;
}
T kth_smallest(u32 l, u32 r, u32 k) const {
assert(l <= r and int(r) <= n);
assert(k < r - l);
T res = 0;
for(int h = lg - 1; h >= 0; --h) {
const u32 l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
if(k < r0 - l0)
l = l0, r = r0;
else {
k -= r0 - l0;
res |= (T)1 << h;
l += bv[h].zeros - l0;
r += bv[h].zeros - r0;
}
}
return res;
}
T kth_largest(const int l, const int r, const int k) const {
assert(0 <= l and l <= r and r <= n);
assert(0 <= k and k < r - l);
return kth_smallest(l, r, r - l - k - 1);
}
int range_freq(int l, int r, const T& upper) const {
assert(0 <= l and l <= r and r <= n);
if(upper <= 0) return 0;
if(lg < (int)numeric_limits<T>::digits and upper >= (T(1) << lg)) return r - l;
int ret = 0;
for(int h = lg - 1; h >= 0; --h) {
const bool f = (upper >> h) & 1;
const u32 l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
if(f) {
ret += r0 - l0;
l += bv[h].zeros - l0;
r += bv[h].zeros - r0;
} else {
l = l0;
r = r0;
}
}
return ret;
}
int range_freq(const int l, const int r, const T& lower, const T& upper) const {
assert(0 <= l and l <= r and r <= n);
assert(lower <= upper);
return range_freq(l, r, upper) - range_freq(l, r, lower);
}
T prev_value(const int l, const int r, const T& upper) const {
assert(0 <= l and l <= r and r <= n);
const int cnt = range_freq(l, r, upper);
return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);
}
T next_value(const int l, const int r, const T& lower) const {
assert(0 <= l and l <= r and r <= n);
const int cnt = range_freq(l, r, lower);
return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);
}
};
#line 4 "verify/unit_test/data_structure/wavelet_matrix.test.cpp"
int main() {
{
WaveletMatrix<int> wm(vector<int>{});
assert(wm.range_freq(0, 0, -1) == 0);
assert(wm.range_freq(0, 0, 0) == 0);
assert(wm.range_freq(0, 0, 10) == 0);
assert(wm.prev_value(0, 0, 10) == -1);
assert(wm.next_value(0, 0, 0) == -1);
}
{
WaveletMatrix<int> wm(5);
for(int i = 0; i < 5; ++i) wm.set(i, i * i % 7);
wm.build();
assert(wm.get(0) == 0);
assert(wm.get(1) == 1);
assert(wm.get(2) == 4);
assert(wm.get(3) == 2);
assert(wm.get(4) == 2);
}
mt19937 mt(0);
for(int n = 0; n <= 80; ++n) {
vector<int> a(n);
for(int& x : a) x = mt() % 32;
WaveletMatrix<int> wm(a);
for(int l = 0; l <= n; ++l) {
for(int r = l; r <= n; ++r) {
vector<int> b(a.begin() + l, a.begin() + r);
sort(b.begin(), b.end());
for(int upper = -2; upper <= 35; ++upper) {
const int freq = lower_bound(b.begin(), b.end(), upper) - b.begin();
assert(wm.range_freq(l, r, upper) == freq);
if(upper >= 0) assert(wm.range_freq(l, r, 0, upper) == freq);
const int less = lower_bound(b.begin(), b.end(), upper) - b.begin();
assert(wm.prev_value(l, r, upper) == (less == 0 ? -1 : b[less - 1]));
assert(wm.next_value(l, r, upper) == (less == (int)b.size() ? -1 : b[less]));
}
for(int k = 0; k < (int)b.size(); ++k) {
assert(wm.kth_smallest(l, r, k) == b[k]);
assert(wm.kth_largest(l, r, k) == b[(int)b.size() - 1 - k]);
}
}
}
}
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}