fork download
  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
stdin
Standard input is empty
stdout
==== 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