| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
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!
For an online algorithm try a treap (or any BBST).
How exactly can you use a treap to do the reverse operations?
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;
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?
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).
Thank you very much for this, I will check it out! :)