#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<size_t len>
class Rolling_Hash_Base : public array<uint64_t, len>{
private:
static constexpr uint64_t add(uint64_t a, uint64_t b){
a+=b+1;
a = (a&mod) + (a>>61);
return a-1;
}
static constexpr uint64_t sub(uint64_t a, uint64_t b){
return add(a, mod-b);
}
static constexpr uint64_t modmul(uint64_t a, uint64_t b){
uint64_t l1 = (uint32_t)a, h1 = a>>32, l2 = (uint32_t)b, h2 = b>>32;
uint64_t l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
uint64_t ret = (l&mod) + (l>>61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
ret = (ret & mod) + (ret>>61);
ret = (ret & mod) + (ret>>61);
return ret-1;
}
static const array<uint64_t, len> base;
static array<uint64_t, len>const& get_base_pow(int exp){
assert(exp>=0);
static vector<array<uint64_t, len> > base_pow;
if((int)base_pow.size() <= exp){
if(base_pow.empty()){
base_pow.reserve(1001);
base_pow.emplace_back();
for(auto &e:base_pow.back()) e = 1;
}
for(int it=base_pow.size(); it<exp+1000;++it){
base_pow.push_back(base_pow.back());
auto &e = base_pow.back();
for(size_t i=0;i<len;++i){
e[i] = modmul(e[i], base[i]);
}
}
}
return base_pow[exp];
}
public:
static constexpr uint64_t mod = (1ull<<61) - 1;
Rolling_Hash_Base() : array<uint64_t, len>{} {};
Rolling_Hash_Base(Rolling_Hash_Base const&o) = default;
Rolling_Hash_Base& operator=(Rolling_Hash_Base const&o) = default;
static array<uint64_t, len> gen_base(){
//seed_seq seed{(uint32_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(), (uint32_t)random_device()(), (uint32_t)4730921};
seed_seq seed{(uint32_t)492214};
mt19937 rng(seed);
array<uint64_t, len> ret;
for(auto &e:ret) e = uniform_int_distribution<uint64_t>(0, mod-1)(rng);
return ret;
}
static vector<Rolling_Hash_Base> hashify(string const&s){
vector<Rolling_Hash_Base> ret;
ret.reserve(s.size()+1);
ret.push_back(Rolling_Hash_Base());
for(char const&e:s){
ret.push_back(ret.back() + e);
}
return ret;
}
template<typename T, typename enable_if<is_integral<T>::value, int>::type = 0>
Rolling_Hash_Base& operator+=(T const&o){
for(size_t i=0;i<len;++i){
(*this)[i] = add(modmul((*this)[i], base[i]), static_cast<uint64_t>(o));
}
++length;
return *this;
}
template<typename T, typename enable_if<is_integral<T>::value, int>::type = 0>
Rolling_Hash_Base operator+(T const&o)const{
Rolling_Hash_Base ret(*this);
ret+=o;
return ret;
}
Rolling_Hash_Base& operator-=(Rolling_Hash_Base const&o){
assert(length >= o.length);
auto const&base_pow = get_base_pow(length - o.length);
//cerr << length << " - " << o.length << "\n";
for(size_t i=0;i<len;++i){
(*this)[i] = sub((*this)[i], modmul(o[i], base_pow[i]));
}
length-=o.length;
return *this;
}
Rolling_Hash_Base operator-(Rolling_Hash_Base const&o)const{
Rolling_Hash_Base ret(*this);
ret-=o;
return ret;
}
size_t length = 0;
};
template<size_t len>
const array<uint64_t, len> Rolling_Hash_Base<len>::base = Rolling_Hash_Base<len>::gen_base();
using Rolling_Hash = Rolling_Hash_Base<2>;
class Treap {
public:
struct Node {
Node*l = nullptr, *r = nullptr;
uint64_t y;
int x;
Node() : y(0), x(-1) {}
Node(int x_, uint64_t y_) : y(y_), x(x_) {}
};
Treap(int n, function<uint64_t(int)> seed) : roots(n), nodes(n){
for(int i=0;i<n;++i){
nodes[i] = Node(i, seed(i));
roots[i] = &nodes[i];
}
}
int merge(int const i, int const j){
roots[i] = merge(roots[i], roots[j]);
roots[j] = nullptr;
free_roots.push_back(j);
return i;
}
pair<int, int> split(int const i, int const x){
assert(!free_roots.empty());
const int j = free_roots.back(); free_roots.pop_back();
tie(roots[i], roots[j]) = split(roots[i], x);
return make_pair(i, j);
}
Rolling_Hash hash(int i){
Rolling_Hash ret;
hash(roots[i], ret);
return ret;
}
uint64_t get_calls() const { return calls; }
void reset_calls() { calls = 0; }
private:
pair<Node*, Node*> split(Node *u, int x){
++calls;
if(!u) return {nullptr, nullptr};
if(x <= u->x){
auto tmp = split(u->l, x);
u->l = tmp.second;
return {tmp.first, u};
} else {
auto tmp = split(u->r, x);
u->r = tmp.first;
return {u, tmp.second};
}
}
Node* join(Node *l, Node *r){
++calls;
if(!l) return r;
if(!r) return l;
if(l->y < r->y){
l->r = join(l->r, r);
return l;
} else {
r->l = join(l, r->l);
return r;
}
}
Node* merge(Node *u, Node *v){
++calls;
if(!u) return v;
if(!v) return u;
if(u->y > v->y) swap(u, v);
auto tmp = split(v, u->x);
u->l = merge(u->l, tmp.first);
u->r = merge(u->r, tmp.second);
return u;
}
void hash(Node*u, Rolling_Hash &h){
if(u){
if(u->l) assert(u->y <= u->l->y);
if(u->r) assert(u->y <= u->r->y);
hash(u->l, h);
h += u->x;
hash(u->r, h);
}
}
vector<int> free_roots;
vector<Node*> roots;
vector<Node> nodes;
uint64_t calls = 0;
};
struct Sparse_Sement_tree{
struct Node{
Node *l, *r;
Node() : l(nullptr), r(nullptr) {}
};
Sparse_Sement_tree(int n_, function<uint64_t(int)>) : n(n_), roots(n){
for(int i=0;i<n;++i){
roots[i] = build(i, 0, n-1);
}
}
int merge(int const i, int const j){
roots[i] = merge(roots[i], roots[j]);
roots[j] = nullptr;
free_roots.push_back(j);
return i;
}
pair<int, int> split(int const i, int const x){
assert(!free_roots.empty());
const int j = free_roots.back(); free_roots.pop_back();
tie(roots[i], roots[j]) = split(roots[i], 0, n-1, x);
return make_pair(i, j);
}
Rolling_Hash hash(int i){
Rolling_Hash ret;
hash(roots[i], 0, n-1, ret);
return ret;
}
uint64_t get_calls() const { return calls; }
void reset_calls() { calls = 0; }
private:
Node* build(int x, int l, int r){
++calls;
if(x < l || x > r) return nullptr;
Node* ret = new Node();
if(l != r){
ret->l = build(x, l, (r+l)/2);
ret->r = build(x, (r+l)/2+1, r);
}
return ret;
}
Node* merge(Node*u, Node*v){
++calls;
if(!u) return v;
if(!v) return u;
u->l = merge(u->l, v->l);
u->r = merge(u->r, v->r);
delete v;
return u;
}
pair<Node*, Node*> split(Node*u, int l, int r, int x){
++calls;
if(!u) return {nullptr, nullptr};
if(l == r){
if(l<x) return {u, nullptr};
return {nullptr, u};
}
const int m = (l+r)/2;
auto v = new Node();
if(x <= m){
auto tmp = split(u->l, l, m, x);
u->l = tmp.second;
v->l = tmp.first;
return {v, u};
} else {
auto tmp = split(u->r, m+1, r, x);
u->r = tmp.first;
v->r = tmp.second;
return {u, v};
}
}
void hash(Node*u, int l, int r, Rolling_Hash &h){
if(!u) return;
if(l == r){
h += l;
} else {
hash(u->l, l, (l+r)/2, h);
hash(u->r, (l+r)/2+1, r, h);
}
}
int n;
vector<int> free_roots;
vector<Node*> roots;
uint64_t calls = 0;
};
template<typename T>
void test_1(const int n, const int iterations, const bool do_hash){
mt19937 rng(1234);
auto get_rand = [&](int l, int r){
return uniform_int_distribution<int>(l, r)(rng);
}; (void)get_rand;
Rolling_Hash expected_total_hash;
uint64_t calls = 0, operations = 0;
for(int trial=0;trial<iterations;++trial){
mt19937 tree_rng(trial);
Rolling_Hash total_hash;
T tree(n, [&](int) -> uint64_t{return uniform_int_distribution<uint64_t>(numeric_limits<uint64_t>::min(), numeric_limits<uint64_t>::max())(tree_rng);});
auto add_hash = [&](int i){
if(do_hash){
auto ha = tree.hash(i);
for(auto const&e:ha) total_hash += e;
}
};
vector<int> roots(n, 0);
iota(roots.begin(), roots.end(), 0);
while(roots.size() > 1){
const int m = roots.size();
const int k = m/2;
for(int i = 0;i<k;++i){
roots[i] = tree.merge(roots[i], roots[i + m-k]), ++operations;
add_hash(roots[i]);
}
roots.erase(roots.begin() + m-k, roots.end());
}
//cerr << "trial " << trial << ", size: " << n << ", hash: " << total_hash[0] << "\n";
if(trial > 0){
assert(total_hash == expected_total_hash);
}
expected_total_hash = total_hash;
calls += tree.get_calls();
}
//const double avg_calls = calls/(double) iterations;
// cerr << "Test 1: " << n << " : " << avg_calls << "\n";
// if(do_hash) cerr << " hash: " << expected_total_hash[0] << "\n";
cerr << " calls / operation: " << calls / (double) operations << "\n";
}
template<typename T>
void test_batch_1(){
cerr << "==== " << typeid(T).name() << " ====\n";
for(int k = 6; k<15; ++k){
const int n = 1<<k;
test_1<T>(n, 10, k <= 8);
}
}
template<typename T>
void test_2(const int N, const int iterations, const bool do_hash){
const int sqrt_n = sqrtl(N);
const int n = sqrt_n * sqrt_n;
mt19937 rng(1234);
auto get_rand = [&](int l, int r){
return uniform_int_distribution<int>(l, r)(rng);
}; (void)get_rand;
Rolling_Hash expected_total_hash;
uint64_t calls = 0, operations = 0;
for(int trial=0;trial<iterations;++trial){
mt19937 tree_rng(trial);
Rolling_Hash total_hash;
T tree(n, [&](int) -> uint64_t{return uniform_int_distribution<uint64_t>(numeric_limits<uint64_t>::min(), numeric_limits<uint64_t>::max())(tree_rng);});
auto add_hash = [&](int i){
if(do_hash){
auto ha = tree.hash(i);
for(auto const&e:ha) total_hash += e;
}
};
// setup single set
int root = 0;
for(int i=1;i<n;++i){
root = tree.merge(root, i), ++operations;
add_hash(root);
}
for(int it=0;it<sqrt_n;++it){
// build sqrt_n blocks of size sqrt_n
vector<int> roots(sqrt_n);
for(int i=sqrt_n-1; i>0; --i){
tie(root, roots[i]) = tree.split(root, i*sqrt_n), ++operations;
add_hash(roots[i]);
}
roots[0] = root;
// then merge blocks again
while(roots.size() > 1){
const int m = roots.size();
const int k = m/2;
for(int i = 0;i<k;++i){
roots[i] = tree.merge(roots[i], roots[i + m-k]), ++operations;
add_hash(i);
}
roots.erase(roots.begin() + m-k, roots.end());
}
}
//cerr << "trial " << trial << ", size: " << n << ", hash: " << total_hash[0] << "\n";
if(trial > 0){
assert(total_hash == expected_total_hash);
}
expected_total_hash = total_hash;
calls += tree.get_calls();
}
const double avg_calls = calls/(double) iterations;
cerr << "Test 2: " << n << " : " << fixed << avg_calls << "\n";
if(do_hash) cerr << " hash: " << expected_total_hash[0] << "\n";
cerr << " calls / operation: " << calls / (double) operations << "\n";
}
template<typename T>
void test_batch_2(){
cerr << "==== " << typeid(T).name() << " ====\n";
for(int k = 5; k<16; ++k){
const int n = 1<<k;
test_2<T>(n, 10, k <= 8);
}
}
int main() {
cerr.rdbuf(cout.rdbuf());
//test_batch_1<Treap>();
//test_batch_1<Sparse_Sement_tree>();
test_batch_2<Treap>();
test_batch_2<Sparse_Sement_tree>();
return 0;
}