title: How does a treap help to update this ordered queue?
body: <p>I'm having trouble understanding this <a href="http://solorab.net/blog/2016/06/05/hackerrank-zalando-codesprint-give-me-the-order/" rel="nofollow">solution</a> to a <a href="https://www.hackerrank.com/contests/zalando-codesprint/challenges/give-me-the-order" rel="nofollow">problem</a> on HackerRank. Please see the solution code below, apparently by Kimiyuki Onaka.</p>
  
  <p>The problem is: given a list of unique numbers, and <code>m</code> queries of the type, "<code>move the current ith to jth elements (l,r) to the beginning</code>", return the final arrangement of the numbers.</p>
  
  <p>Onaka suggests that a treap data structure (one that maintains both priority and binary search) can help solve it in <code>O(m log n)</code>. Since I'm not versed in C++, I've tried but failed to conceptualize how a treap could be used. My understanding is that to solve the problem you need <code>log</code> time access to the current <code>ith to jth</code> elements and <code>log</code> time update of the current first element/s and overall order. But I can't see how to conceptualize it.</p>
  
  <p>Ideally, I'd like an explanation in words of how it could be done. Alternatively, just an explanation of what Onaka's code is doing.</p>
  
  <p>Thanks! </p>
  
  <pre class="lang-cpp prettyprint-override"><code>#include &lt;iostream&gt;
  #include &lt;tuple&gt;
  #include &lt;random&gt;
  #include &lt;memory&gt;
  #define repeat(i,n) for (int i = 0; (i) &lt; (n); ++(i))
  using namespace std;
  
  template &lt;typename T&gt;
  struct treap {
      typedef T value_type;
      typedef double key_type;
      value_type v;
      key_type k;
      shared_ptr&lt;treap&gt; l, r;
      size_t m_size;
      treap(value_type v)
              : v(v)
              , k(generate())
              , l()
              , r()
              , m_size(1) {
      }
      static shared_ptr&lt;treap&gt; update(shared_ptr&lt;treap&gt; const &amp; t) {
          if (t) {
              t-&gt;m_size = 1 + size(t-&gt;l) + size(t-&gt;r);
          }
          return t;
      }
      static key_type generate() {
          static random_device device;
          static default_random_engine engine(device());
          static uniform_real_distribution&lt;double&gt; dist;
          return dist(engine);
      }
      static size_t size(shared_ptr&lt;treap&gt; const &amp; t) {
          return t ? t-&gt;m_size : 0;
      }
      static shared_ptr&lt;treap&gt; merge(shared_ptr&lt;treap&gt; const &amp; a, shared_ptr&lt;treap&gt; const &amp; b) { // destructive
          if (not a) return b;
          if (not b) return a;
          if (a-&gt;k &gt; b-&gt;k) {
              a-&gt;r = merge(a-&gt;r, b);
              return update(a);
          } else {
              b-&gt;l = merge(a, b-&gt;l);
              return update(b);
          }
      }
      static pair&lt;shared_ptr&lt;treap&gt;, shared_ptr&lt;treap&gt; &gt; split(shared_ptr&lt;treap&gt; const &amp; t, size_t i) { // [0, i) [i, n), destructive
          if (not t) return { shared_ptr&lt;treap&gt;(), shared_ptr&lt;treap&gt;() };
          if (i &lt;= size(t-&gt;l)) {
              shared_ptr&lt;treap&gt; u; tie(u, t-&gt;l) = split(t-&gt;l, i);
              return { u, update(t) };
          } else {
              shared_ptr&lt;treap&gt; u; tie(t-&gt;r, u) = split(t-&gt;r, i - size(t-&gt;l) - 1);
              return { update(t), u };
          }
      }
      static shared_ptr&lt;treap&gt; insert(shared_ptr&lt;treap&gt; const &amp; t, size_t i, value_type v) { // destructive
          shared_ptr&lt;treap&gt; l, r; tie(l, r) = split(t, i);
          shared_ptr&lt;treap&gt; u = make_shared&lt;treap&gt;(v);
          return merge(merge(l, u), r);
      }
      static pair&lt;shared_ptr&lt;treap&gt;,shared_ptr&lt;treap&gt; &gt; erase(shared_ptr&lt;treap&gt; const &amp; t, size_t i) { // (t \ t_i, t_t), destructive
          shared_ptr&lt;treap&gt; l, u, r;
          tie(l, r) = split(t, i+1);
          tie(l, u) = split(l, i);
          return { merge(l, r), u };
      }
  };
  
  typedef treap&lt;int&gt; T;
  int main() {
      int n; cin &gt;&gt; n;
      shared_ptr&lt;T&gt; t;
      repeat (i,n) {
          int a; cin &gt;&gt; a;
          t = T::insert(t, i, a);
      }
      int m; cin &gt;&gt; m;
      while (m --) {
          int l, r; cin &gt;&gt; l &gt;&gt; r;
          -- l;
          shared_ptr&lt;T&gt; a, b, c;
          tie(a, c) = T::split(t, r);
          tie(a, b) = T::split(a, l);
          t = T::merge(T::merge(b, a), c);
      }
      repeat (i,n) {
          if (i) cout &lt;&lt; ' ';
          shared_ptr&lt;T&gt; u;
          tie(t, u) = T::erase(t, 0);
          cout &lt;&lt; u-&gt;v;
      }
      cout &lt;&lt; endl;
      return 0;
  }
  </code></pre>