Author: Zi Song Yeoh
IMPLICIT TREAPS, SPLAY TREES (or any other BBST)
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.
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.