PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
MEDIUM
PREREQUISITES:
IMPLICIT TREAPS, SPLAY TREES (or any other BBST)
PROBLEM:
There are 3 operations you can do to a string s :
-
Cut [l, r] and paste it after position pos.
-
Apply a cyclic shift to [l, r] c times.
-
Reverse the substring [l, r].
Determine the final string after Q operations.
EXPLANATION:
This is a giveaway problem. One of the possible data structures that can solve this problem is implicit treap. You can find a good tutorial here and here.
Now, we can treat each character as an element of the treap and the first query is equivalent to cutting and merging some vertices of the treap, the second and third query can be done with lazy propogation with implicit treaps, whereas when we need to reverse a segment we only have to swap the two childrens and flip their reverse counter. You can see the sample code for details on how to implement this.
The complexity is O(Q\log n).
Initially, a square root decomposition solution was intended but then we realized implicit treaps can also solve this problem easily.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.