askhelper's blog

Interesting problem
By askhelper, 6 years ago, In English

Hello Codeforces. I'm interested in this problem, and I actually came up with this. It seems standard, but unfortunately, I couldn't get any results from the internet. So the statement follows:

We have a cycle of numbers (1, 2, 3, ..., n) arranged like . Also, we need to do queries reversing a part of the cycle. For example, if the cycle is , and if query is the (3, 1) (reverse path from 3 to 1), the new cycle will be: . After all these queries, we need to print the new cycle. Note that we don't have any "ask" queries. Constraints are about 105.

Thanks in advance.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Are you familiar with treaps?

They (and similar structures) are one of the most universal ways to deal with such problems, in that they are so often applicable. With some tinkering, this problem too can be solved using a treap.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought if there are no any "ask" queries (like demanding i'th element of a cycle) problem can be solved without any complex data structures as treap. Anyway, I would like to know how to handle these queries with treap.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      No "ask" queries is only really useful if the queries can be carried out in an "amortized" fashion, and I couldn't find anything like that.

      Anyway, let us first get rid of the fact that the thing is a cycle. Arrays are much more convenient. Let's break the cycle at some arbitrary point. Now, instead of ... 7 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 1... we talk about 1 → 2 → 3 → 4 → 5 → 6 → 7. If we come across a query like (6, 2), we can simply emulate that by reversing (3, 5) and then reversing the whole array.

      Using a treap, we can quickly reverse subarrays of the given array. We need three treap operations:

      • split, which splits the treap into two at any given point;

      • merge, which merges two treaps;

      • reverse, which reverses the entire treap.

      Split and merge are common, so I'll talk about reverse for a bit. To reverse a treap, the whole treap, we just need to swap the left and right child of every node in the treap. We can't swap them all at the same time though, because that would take too much time. We can, however, use lazy propagation. Just put a note to the root of the treap that its children need to be reversed. The next time when the roots children are relevant, the swapping is done and the note is passed on to the children.

      → Reply