themaskedhero's blog

Reversing String Queries
By themaskedhero, history, 8 years ago, In English

Hi CF community!

I was thinking about some problem:

Given a string S, in each query you must reverse some substring of it. Then, at the end you must print the string. Constraints are 1 ≤ |S|, Q ≤ 105 where Q is number of string reversals.

I'm now wondering about what is the offline and the online algorithms to solve this problem.

Thanks!

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

»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

For an online algorithm try a treap (or any BBST).

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

    How exactly can you use a treap to do the reverse operations?

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

      treap and splay tree can be used, each node have a bool lazy_reverse value that can be propagated to sons, if this value is true, then swap( left_son , right_son ) propagate: left_son.lazy_reverse ^= nod.lazy_reverse; ritgh_son.lazy_reverse ^= nod.lazy_reverse;

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

    Can we really use any BBST? I know about treap but this works because in a treap you can extract the whole interval you need with split operations and this is what makes just swapping the left and the right children work correctly. How can we do this with AVL tree, for example, please elaborate if possible?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      You can split an AVL too (it doesn't seem trivial but it is possible : avl split).

      Maybe any BBST was not the best statement (it seems that you can split any BST in O(logn * loglogn) but I didn't do a lot of research on this topic).

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

        Thank you very much for this, I will check it out! :)

        → Reply