Advertisement
Guest User

Untitled

a guest
Oct 31st, 2017
1,052
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct SegmTree {
  6.     string name = "SegmTree";
  7.     map<int, int> roots;
  8.  
  9.     struct Node {
  10.         int l = 0, r = 0, sz = 0;
  11.     };
  12.     vector<Node> T = {{}};
  13.     int n;
  14.  
  15.     int build(int b, int e, int pos) {
  16.         int ret = T.size(); T.emplace_back();
  17.         T[ret].sz = 1;
  18.  
  19.         if (b != e) {
  20.             int m = (b + e) / 2;
  21.             if (pos <= m) T[ret].l = build(b, m, pos);
  22.             else T[ret].r = build(m + 1, e, pos);
  23.         }
  24.         return ret;
  25.     }
  26.  
  27.     void update(int node) {
  28.         T[node].sz = T[T[node].l].sz + T[T[node].r].sz;
  29.     }
  30.  
  31.  
  32.     pair<int, int> split(int node, int k) {
  33.         int lsz = T[T[node].l].sz, l = node, r = T.size();
  34.         T.emplace_back();
  35.  
  36.         if (k > lsz) tie(T[l].r, T[r].r) = split(T[l].r, k - lsz);
  37.         else swap(T[l].r, T[r].r);
  38.         if (k < lsz) tie(T[l].l, T[r].l) = split(T[l].l, k);
  39.         update(l); update(r);
  40.         return {l, r};
  41.     }
  42.  
  43.     int merge(int a, int b) {
  44.         if (!a or !b) return (a | b);
  45.        
  46.         T[a].l = merge(T[a].l, T[b].l);
  47.         T[a].r = merge(T[a].r, T[b].r);
  48.         update(a);
  49.         return a;
  50.     }
  51.  
  52.     SegmTree(vector<int>& V) : n(V.size()) {
  53.         for (int i = 0; i < n; ++i)
  54.             roots[i] = build(0, n - 1, V[i]);
  55.         roots[n] = 0;
  56.     }
  57.  
  58.     void split_for(int x) {
  59.         auto it = prev(roots.upper_bound(x));
  60.         if (it->first != x) {
  61.             tie(it->second, roots[x]) = split(it->second, x - it->first);
  62.         }
  63.     }
  64.     void Sort(int b, int e) {
  65.         if (b == e) return;
  66.         split_for(b); split_for(e);
  67.         auto it = roots.find(b);
  68.        
  69.         int jn = 0;
  70.         while (it->first != e) {
  71.             jn = merge(jn, it->second);
  72.             ++it; roots.erase(prev(it));
  73.         }
  74.         assert(T[jn].sz == (e - b));
  75.         roots[b] = jn;
  76.     }
  77.  
  78.     vector<int> ret;
  79.     void dump(int node, int b, int e) {
  80.         if (node == 0) return;
  81.         if (b == e) { ret.push_back(b); return; }
  82.         int m = (b + e) / 2;
  83.         dump(T[node].l, b, m);
  84.         dump(T[node].r, m + 1, e);
  85.     }
  86.  
  87.     vector<int> Dump() {
  88.         ret.clear();
  89.         for (auto p : roots) {
  90.             dump(p.second, 0, n - 1);
  91.         }
  92.         return ret;
  93.     }
  94. };
  95.  
  96. struct Treap {
  97.     string name = "Treap";
  98.     map<int, int> roots;
  99.     int n;
  100.  
  101.     struct Node {
  102.         int l = 0, r = 0, k = 0, p = 0, sz = 0;
  103.     };
  104.     vector<Node> T;
  105.  
  106.     void update(int node) {
  107.         if (node == 0) return;
  108.         T[node].sz = 1 + T[T[node].l].sz + T[T[node].r].sz;
  109.     }
  110.  
  111.  
  112.     pair<int, int> split(int node, int k) {
  113.         if (k == 0) return {0, node};
  114.        
  115.         int lsz = T[T[node].l].sz, l, r;
  116.        
  117.         if (k > lsz)
  118.             tie(T[node].r, r) = split(T[node].r, k - lsz - 1), l = node;
  119.         else tie(l, T[node].l) = split(T[node].l, k), r = node;
  120.  
  121.         update(node);
  122.         return {l, r};
  123.     }
  124.  
  125.     pair<int, int> splitk(int node, int k) {
  126.         if (node == 0) return {0, 0};
  127.  
  128.         int l, r;
  129.         if (T[node].k < k)
  130.             tie(T[node].r, r) = splitk(T[node].r, k), l = node;
  131.         else tie(l, T[node].l) = splitk(T[node].l, k), r = node;
  132.        
  133.         update(node);
  134.         return {l, r};
  135.     }
  136.  
  137.     int merge(int a, int b) {
  138.         if (!a or !b) return a + b;
  139.        
  140.         if (T[a].p < T[b].p) swap(a, b);
  141.         int l, r;
  142.         tie(l, r) = splitk(b, T[a].k);
  143.         T[a].l = merge(T[a].l, l);
  144.         T[a].r = merge(T[a].r, r);
  145.  
  146.         update(a);
  147.         return a;
  148.     }
  149.  
  150.     Treap(vector<int>& V) : n(V.size()), T(n + 1) {
  151.         for (int i = 0; i < n; ++i) {
  152.             T[i + 1].k = V[i];
  153.             T[i + 1].p = rand() + 1;
  154.             update(i + 1);
  155.             roots[i] = i + 1;
  156.         }
  157.         roots[n] = 0;
  158.     }
  159.  
  160.     void split_for(int x) {
  161.         auto it = prev(roots.upper_bound(x));
  162.         if (it->first != x) {
  163.             tie(it->second, roots[x]) = split(it->second, x - it->first);
  164.         }
  165.     }
  166.     void Sort(int b, int e) {
  167.         if (b == e) return;
  168.         split_for(b); split_for(e);
  169.         auto it = roots.find(b);
  170.  
  171.         int jn = 0;
  172.         while (it->first != e) {
  173.             jn = merge(jn, it->second);
  174.             ++it; roots.erase(prev(it));
  175.         }
  176.         assert(T[jn].sz == (e - b));
  177.         roots[b] = jn;
  178.     }
  179.  
  180.     vector<int> ret;
  181.     void dump(int node) {
  182.         if (node == 0) return;
  183.         dump(T[node].l);
  184.         ret.push_back(T[node].k);
  185.         dump(T[node].r);
  186.     }
  187.  
  188.     vector<int> Dump() {
  189.         ret.clear();
  190.         for (auto p : roots) {
  191.             dump(p.second);
  192.         }
  193.         return ret;
  194.     }
  195. };
  196.  
  197. struct Brut {
  198.     string name = "Brut";
  199.     vector<int> V;
  200.     Brut(vector<int> V) : V(V) {}
  201.     void Sort(int b, int e) {
  202.         sort(V.begin() + b, V.begin() + e);
  203.     }
  204.     vector<int> Dump() { return V; }
  205. };
  206.  
  207. template<typename T>
  208. ostream& operator<<(ostream& out, vector<T>& V) {
  209.     for (auto x : V) out << x << " ";
  210.     return out;
  211. }
  212.  
  213. template<typename Solver> vector<int> Check(vector<int> V, vector<complex<int>> ops) {
  214.     time_t tick = clock();
  215.     Solver solver(V);
  216.     for (auto op : ops) {
  217.         solver.Sort(op.real(), op.imag());
  218.     }
  219.     auto got = solver.Dump();
  220.     time_t tock = clock();
  221.     cerr << solver.name << " time: " << 1.0 * (tock - tick) / CLOCKS_PER_SEC << endl;
  222.     return got;
  223. }
  224.  
  225. int main() {
  226.     int its = 0;
  227.     while (true) {
  228.    
  229.         int sz = 1 + rand() % 500000;
  230.         vector<int> V(sz);
  231.         for (int i = 0; i < sz; ++i)
  232.             V[i] = i;
  233.         random_shuffle(V.begin(), V.end());
  234.  
  235.         vector<complex<int>> ops;
  236.        
  237.         int opc = rand() % 80000 + 1;
  238.         for (int i = 0; i < opc; ++i) {
  239.             int b = rand() % sz;
  240.             int e = rand() % (sz + 1);
  241.             if (b > e) swap(b, e);
  242.             ops.emplace_back(b, e);
  243.         }
  244.  
  245.         auto resb = Check<Brut>(V, ops);
  246.         auto rest = Check<Treap>(V, ops);
  247.         auto ress = Check<SegmTree>(V, ops);
  248.        
  249.         if (resb != rest or resb != ress) {
  250.             cerr << "Initial: " << V << endl;
  251.             cerr << "Brut: " << resb << endl;
  252.             cerr << "Treap: " << rest << endl;
  253.             cerr << "SegmTree: " << ress << endl;
  254.         }
  255.        
  256.         if ((++its) % 1 == 0) {
  257.             cerr << "OK " << its << " iterations" << endl << endl;
  258.         }
  259.     }
  260.     return 0;
  261. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement