fork download
copy 
  1. #undef _GLIBCXX_DEBUG
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. template<size_t len>
  9. class Rolling_Hash_Base : public array<uint64_t, len>{
  10. private:
  11.     static constexpr uint64_t add(uint64_t a, uint64_t b){
  12.         a+=b+1;
  13.         a = (a&mod) + (a>>61);
  14.         return a-1;
  15.     }
  16.     static constexpr uint64_t sub(uint64_t a, uint64_t b){
  17.         return add(a, mod-b);
  18.     }
  19.     static constexpr uint64_t modmul(uint64_t a, uint64_t b){
  20.         uint64_t l1 = (uint32_t)a, h1 = a>>32, l2 = (uint32_t)b, h2 = b>>32;
  21.         uint64_t l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
  22.         uint64_t ret = (l&mod) + (l>>61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  23.         ret = (ret & mod) + (ret>>61);
  24.         ret = (ret & mod) + (ret>>61);
  25.         return ret-1;
  26.     }
  27.     static const array<uint64_t, len> base;
  28.     static array<uint64_t, len>const& get_base_pow(int exp){
  29.         assert(exp>=0);
  30.         static vector<array<uint64_t, len> > base_pow;
  31.         if((int)base_pow.size() <= exp){
  32.             if(base_pow.empty()){
  33.                 base_pow.reserve(1001);
  34.                 base_pow.emplace_back();
  35.                 for(auto &e:base_pow.back()) e = 1;
  36.             }
  37.             for(int it=base_pow.size(); it<exp+1000;++it){
  38.                 base_pow.push_back(base_pow.back());
  39.                 auto &e = base_pow.back();
  40.                 for(size_t i=0;i<len;++i){
  41.                     e[i] = modmul(e[i], base[i]);
  42.                 }
  43.             }
  44.         }
  45.         return base_pow[exp];
  46.     }
  47.  
  48. public:
  49.     static constexpr uint64_t mod = (1ull<<61) - 1;
  50.  
  51.     Rolling_Hash_Base() : array<uint64_t, len>{} {};
  52.     Rolling_Hash_Base(Rolling_Hash_Base const&o) = default;
  53.     Rolling_Hash_Base& operator=(Rolling_Hash_Base const&o) = default;
  54.  
  55.     static array<uint64_t, len> gen_base(){
  56.         //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};
  57.         seed_seq seed{(uint32_t)492214};
  58.         mt19937 rng(seed);
  59.         array<uint64_t, len> ret;
  60.         for(auto &e:ret) e = uniform_int_distribution<uint64_t>(0, mod-1)(rng);
  61.         return ret;
  62.     }
  63.     static vector<Rolling_Hash_Base> hashify(string const&s){
  64.         vector<Rolling_Hash_Base> ret;
  65.         ret.reserve(s.size()+1);
  66.         ret.push_back(Rolling_Hash_Base());
  67.         for(char const&e:s){
  68.             ret.push_back(ret.back() + e);
  69.         }
  70.         return ret;
  71.     }
  72.  
  73.     template<typename T, typename enable_if<is_integral<T>::value, int>::type = 0>
  74.     Rolling_Hash_Base& operator+=(T const&o){
  75.         for(size_t i=0;i<len;++i){
  76.             (*this)[i] = add(modmul((*this)[i], base[i]), static_cast<uint64_t>(o));
  77.         }
  78.         ++length;
  79.         return *this;
  80.     }
  81.     template<typename T, typename enable_if<is_integral<T>::value, int>::type = 0>
  82.     Rolling_Hash_Base operator+(T const&o)const{
  83.         Rolling_Hash_Base ret(*this);
  84.         ret+=o;
  85.         return ret;
  86.     }
  87.     Rolling_Hash_Base& operator-=(Rolling_Hash_Base const&o){
  88.         assert(length >= o.length);
  89.         auto const&base_pow = get_base_pow(length - o.length);
  90.         //cerr << length << " - " << o.length << "\n";
  91.         for(size_t i=0;i<len;++i){
  92.             (*this)[i] = sub((*this)[i], modmul(o[i], base_pow[i]));
  93.         }
  94.         length-=o.length;
  95.         return *this;
  96.     }
  97.     Rolling_Hash_Base operator-(Rolling_Hash_Base const&o)const{
  98.         Rolling_Hash_Base ret(*this);
  99.         ret-=o;
  100.         return ret;
  101.     }
  102.  
  103.     size_t length = 0;
  104. };
  105. template<size_t len>
  106. const array<uint64_t, len> Rolling_Hash_Base<len>::base = Rolling_Hash_Base<len>::gen_base();
  107.  
  108. using Rolling_Hash = Rolling_Hash_Base<2>;
  109.  
  110.  
  111. class Treap {
  112. public:
  113.     struct Node {
  114.         Node*l = nullptr, *r = nullptr;
  115.         uint64_t y;
  116.         int x;
  117.         Node() : y(0), x(-1) {}
  118.         Node(int x_, uint64_t y_) : y(y_),  x(x_) {}
  119.     };
  120.     Treap(int n, function<uint64_t(int)> seed) : roots(n), nodes(n){
  121.         for(int i=0;i<n;++i){
  122.             nodes[i] = Node(i, seed(i));
  123.             roots[i] = &nodes[i];
  124.         }
  125.     }
  126.  
  127.     int merge(int const i, int const j){
  128.         roots[i] = merge(roots[i], roots[j]);
  129.         roots[j] = nullptr;
  130.         free_roots.push_back(j);
  131.         return i;
  132.     }
  133.     pair<int, int> split(int const i, int const x){
  134.         assert(!free_roots.empty());
  135.         const int j = free_roots.back(); free_roots.pop_back();
  136.         tie(roots[i], roots[j]) = split(roots[i], x);
  137.         return make_pair(i, j);
  138.     }
  139.     Rolling_Hash hash(int i){
  140.         Rolling_Hash ret;
  141.         hash(roots[i], ret);
  142.         return ret;
  143.     }
  144.  
  145.     uint64_t get_calls() const { return calls; }
  146.     void reset_calls() { calls = 0; }
  147.  
  148. private:
  149.     pair<Node*, Node*> split(Node *u, int x){
  150.         ++calls;
  151.         if(!u) return {nullptr, nullptr};
  152.         if(x <= u->x){
  153.             auto tmp = split(u->l, x);
  154.             u->l = tmp.second;
  155.             return {tmp.first, u};
  156.         } else {
  157.             auto tmp = split(u->r, x);
  158.             u->r = tmp.first;
  159.             return {u, tmp.second};
  160.         }
  161.     }
  162.     Node* join(Node *l, Node *r){
  163.         ++calls;
  164.         if(!l) return r;
  165.         if(!r) return l;
  166.         if(l->y < r->y){
  167.             l->r = join(l->r, r);
  168.             return l;
  169.         } else {
  170.             r->l = join(l, r->l);
  171.             return r;
  172.         }
  173.     }
  174.     Node* merge(Node *u, Node *v){
  175.         ++calls;
  176.         if(!u) return v;
  177.         if(!v) return u;
  178.         if(u->y > v->y) swap(u, v);
  179.         auto tmp = split(v, u->x);
  180.         u->l = merge(u->l, tmp.first);
  181.         u->r = merge(u->r, tmp.second);
  182.         return u;
  183.     }
  184.     void hash(Node*u, Rolling_Hash &h){
  185.         if(u){
  186.             if(u->l) assert(u->y <= u->l->y);
  187.             if(u->r) assert(u->y <= u->r->y);
  188.             hash(u->l, h);
  189.             h += u->x;
  190.             hash(u->r, h);
  191.         }
  192.     }
  193.  
  194.     vector<int> free_roots;
  195.     vector<Node*> roots;
  196.     vector<Node> nodes;
  197.     uint64_t calls = 0;
  198. };
  199.  
  200. struct Sparse_Sement_tree{
  201.     struct Node{
  202.         Node *l, *r;
  203.         Node() : l(nullptr), r(nullptr) {}
  204.     };
  205.  
  206.     Sparse_Sement_tree(int n_, function<uint64_t(int)>) : n(n_), roots(n){
  207.         for(int i=0;i<n;++i){
  208.             roots[i] = build(i, 0, n-1);
  209.         }
  210.     }
  211.  
  212.     int merge(int const i, int const j){
  213.         roots[i] = merge(roots[i], roots[j]);
  214.         roots[j] = nullptr;
  215.         free_roots.push_back(j);
  216.         return i;
  217.     }
  218.     pair<int, int> split(int const i, int const x){
  219.         assert(!free_roots.empty());
  220.         const int j = free_roots.back(); free_roots.pop_back();
  221.         tie(roots[i], roots[j]) = split(roots[i], 0, n-1, x);
  222.         return make_pair(i, j);
  223.     }
  224.  
  225.  
  226.     Rolling_Hash hash(int i){
  227.         Rolling_Hash ret;
  228.         hash(roots[i], 0, n-1, ret);
  229.         return ret;
  230.     }
  231.  
  232.  
  233.     uint64_t get_calls() const { return calls; }
  234.     void reset_calls() { calls = 0; }
  235.  
  236. private:
  237.     Node* build(int x, int l, int r){
  238.         ++calls;
  239.         if(x < l || x > r) return nullptr;
  240.         Node* ret = new Node();
  241.         if(l != r){
  242.             ret->l = build(x, l, (r+l)/2);
  243.             ret->r = build(x, (r+l)/2+1, r);
  244.         }
  245.         return ret;
  246.     }
  247.     Node* merge(Node*u, Node*v){
  248.         ++calls;
  249.         if(!u) return v;
  250.         if(!v) return u;
  251.         u->l = merge(u->l, v->l);
  252.         u->r = merge(u->r, v->r);
  253.         delete v;
  254.         return u;
  255.     }
  256.     pair<Node*, Node*> split(Node*u, int l, int r, int x){
  257.         ++calls;
  258.         if(!u) return {nullptr, nullptr};
  259.         if(l == r){
  260.             if(l<x) return {u, nullptr};
  261.             return {nullptr, u};
  262.         }
  263.         const int m = (l+r)/2;
  264.         auto v = new Node();
  265.         if(x <= m){
  266.             auto tmp = split(u->l, l, m, x);
  267.             u->l = tmp.second;
  268.             v->l = tmp.first;
  269.             return {v, u};
  270.         } else {
  271.             auto tmp = split(u->r, m+1, r, x);
  272.             u->r = tmp.first;
  273.             v->r = tmp.second;
  274.             return {u, v};
  275.         }
  276.     }
  277.     void hash(Node*u, int l, int r, Rolling_Hash &h){
  278.         if(!u) return;
  279.         if(l == r){
  280.             h += l;
  281.         } else {
  282.             hash(u->l, l, (l+r)/2, h);
  283.             hash(u->r, (l+r)/2+1, r, h);
  284.         }
  285.     }
  286.  
  287.     int n;
  288.     vector<int> free_roots;
  289.     vector<Node*> roots;
  290.     uint64_t calls = 0;
  291. };
  292.  
  293.  
  294. template<typename T>
  295. void test_1(const int n, const int iterations, const bool do_hash){
  296.     mt19937 rng(1234);
  297.     auto get_rand = [&](int l, int r){
  298.         return uniform_int_distribution<int>(l, r)(rng);
  299.     }; (void)get_rand;
  300.     Rolling_Hash expected_total_hash;
  301.     uint64_t calls = 0, operations = 0;
  302.     for(int trial=0;trial<iterations;++trial){
  303.         mt19937 tree_rng(trial);
  304.         Rolling_Hash total_hash;
  305.         T tree(n, [&](int) -> uint64_t{return uniform_int_distribution<uint64_t>(numeric_limits<uint64_t>::min(), numeric_limits<uint64_t>::max())(tree_rng);});
  306.         auto add_hash = [&](int i){
  307.             if(do_hash){
  308.                 auto ha = tree.hash(i);
  309.                 for(auto const&e:ha) total_hash += e;
  310.             }
  311.         };
  312.  
  313.         vector<int> roots(n, 0);
  314.         iota(roots.begin(), roots.end(), 0);
  315.         while(roots.size() > 1){
  316.             const int m = roots.size();
  317.             const int k = m/2;
  318.             for(int i = 0;i<k;++i){
  319.                 roots[i] = tree.merge(roots[i], roots[i + m-k]), ++operations;
  320.                 add_hash(roots[i]);
  321.             }
  322.             roots.erase(roots.begin() + m-k, roots.end());
  323.         }
  324.         //cerr << "trial " << trial << ", size: " << n << ", hash: " << total_hash[0] << "\n";
  325.         if(trial > 0){
  326.             assert(total_hash == expected_total_hash);
  327.         }
  328.         expected_total_hash = total_hash;
  329.         calls += tree.get_calls();
  330.     }
  331.     //const double avg_calls = calls/(double) iterations;
  332.     // cerr << "Test 1: " << n << " : " << avg_calls << "\n";
  333.     // if(do_hash) cerr << "   hash: " << expected_total_hash[0] << "\n";
  334.     cerr << "   calls / operation: " << calls / (double) operations << "\n";
  335. }
  336. template<typename T>
  337. void test_batch_1(){
  338.     cerr << "==== " << typeid(T).name() << " ====\n";
  339.     for(int k = 6; k<15; ++k){
  340.         const int n = 1<<k;
  341.         test_1<T>(n, 10, k <= 8);
  342.     }
  343. }
  344.  
  345. template<typename T>
  346. void test_2(const int N, const int iterations, const bool do_hash){
  347.     const int sqrt_n = sqrtl(N);
  348.     const int n = sqrt_n * sqrt_n;
  349.     mt19937 rng(1234);
  350.     auto get_rand = [&](int l, int r){
  351.         return uniform_int_distribution<int>(l, r)(rng);
  352.     }; (void)get_rand;
  353.     Rolling_Hash expected_total_hash;
  354.     uint64_t calls = 0, operations = 0;
  355.     for(int trial=0;trial<iterations;++trial){
  356.         mt19937 tree_rng(trial);
  357.         Rolling_Hash total_hash;
  358.         T tree(n, [&](int) -> uint64_t{return uniform_int_distribution<uint64_t>(numeric_limits<uint64_t>::min(), numeric_limits<uint64_t>::max())(tree_rng);});
  359.         auto add_hash = [&](int i){
  360.             if(do_hash){
  361.                 auto ha = tree.hash(i);
  362.                 for(auto const&e:ha) total_hash += e;
  363.             }
  364.         };
  365.         // setup single set
  366.         int root = 0;
  367.         for(int i=1;i<n;++i){
  368.             root = tree.merge(root, i), ++operations;
  369.             add_hash(root);
  370.         }
  371.         for(int it=0;it<sqrt_n;++it){
  372.             // build sqrt_n blocks of size sqrt_n
  373.             vector<int> roots(sqrt_n);
  374.             for(int i=sqrt_n-1; i>0; --i){
  375.                 tie(root, roots[i]) = tree.split(root, i*sqrt_n), ++operations;
  376.                 add_hash(roots[i]);
  377.             }
  378.             roots[0] = root;
  379.             // then merge blocks again
  380.             while(roots.size() > 1){
  381.                 const int m = roots.size();
  382.                 const int k = m/2;
  383.                 for(int i = 0;i<k;++i){
  384.                     roots[i] = tree.merge(roots[i], roots[i + m-k]), ++operations;
  385.                     add_hash(i);
  386.                 }
  387.                 roots.erase(roots.begin() + m-k, roots.end());
  388.             }
  389.         }
  390.         //cerr << "trial " << trial << ", size: " << n << ", hash: " << total_hash[0] << "\n";
  391.         if(trial > 0){
  392.             assert(total_hash == expected_total_hash);
  393.         }
  394.         expected_total_hash = total_hash;
  395.         calls += tree.get_calls();
  396.     }
  397.     const double avg_calls = calls/(double) iterations;
  398.     cerr << "Test 2: " << n << " : " << fixed << avg_calls << "\n";
  399.     if(do_hash) cerr << "   hash: " << expected_total_hash[0] << "\n";
  400.     cerr << "   calls / operation: " << calls / (double) operations << "\n";
  401. }
  402. template<typename T>
  403. void test_batch_2(){
  404.     cerr << "==== " << typeid(T).name() << " ====\n";
  405.     for(int k = 5; k<16; ++k){
  406.         const int n = 1<<k;
  407.         test_2<T>(n, 10, k <= 8);
  408.     }
  409. }
  410.  
  411. int main() {
  412. 	cerr.rdbuf(cout.rdbuf());
  413.     //test_batch_1<Treap>();
  414.     //test_batch_1<Sparse_Sement_tree>();
  415.     test_batch_2<Treap>();
  416.     test_batch_2<Sparse_Sement_tree>();
  417.  
  418.     return 0;
  419. }
  420.  
Success #stdin #stdout 3.16s 70976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
==== 5Treap ====
Test 2: 25 : 904.100000
   hash: 968969214953312820
   calls / operation: 14.126563
Test 2: 64 : 3985.800000
   hash: 2268330398328088051
   calls / operation: 22.776000
Test 2: 121 : 9626.900000
   hash: 129872621225605516
   calls / operation: 28.314412
Test 2: 256 : 28473.400000
   hash: 1824792528244595403
   calls / operation: 38.739320
Test 2: 484 : 62428.900000
   calls / operation: 44.370220
Test 2: 1024 : 178706.800000
   calls / operation: 59.430263
Test 2: 2025 : 439100.400000
   calls / operation: 73.379078
Test 2: 4096 : 1080119.900000
   calls / operation: 88.832955
Test 2: 8100 : 2485902.400000
   calls / operation: 103.068220
Test 2: 16384 : 6204047.500000
   calls / operation: 126.885111
Test 2: 32761 : 14344670.400000
   calls / operation: 146.493775
==== 18Sparse_Sement_tree ====
Test 2: 25 : 798.000000
   hash: 968969214953312820
   calls / operation: 12.468750
Test 2: 64 : 2657.000000
   hash: 2268330398328088051
   calls / operation: 15.182857
Test 2: 121 : 5891.000000
   hash: 129872621225605516
   calls / operation: 17.326471
Test 2: 256 : 14433.000000
   hash: 1824792528244595403
   calls / operation: 19.636735
Test 2: 484 : 30711.000000
   calls / operation: 21.827292
Test 2: 1024 : 72705.000000
   calls / operation: 24.178583
Test 2: 2025 : 158309.000000
   calls / operation: 26.455381
Test 2: 4096 : 349825.000000
   calls / operation: 28.770869
Test 2: 8100 : 749243.000000
   calls / operation: 31.064431
Test 2: 16384 : 1632769.000000
   calls / operation: 33.393374
Test 2: 32761 : 3496893.000000
   calls / operation: 35.711734
https://ideone.com/TCxhxt
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!