Блог пользователя themaskedhero

Автор themaskedhero, история, 8 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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;

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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?