Before reading this blog

https://codeforces.me/blog/entry/10355 — I hope you read this blog before reading this blog. Basically, the SGI STL implements the "rope" data structure, which is a tree-based data structure for doing operations in $$$O(\log N)$$$ time complexity. You can read ahead if you are already familiar with the data structure.

Before we start, Let me explain to you the context on how I thought about this "trick". The rope implementation in SGI STL (from which GNU G++ borrows many extensions) provides many operations given on strings. The most important out of them would arguably be substr (Splitting a substring into another rope) and + (Merging two ropes into one, effectively "concatenating" the strings). There are more functions too, but there is no function to reverse a substring.

Now back to my side of the context. I was thinking about a way to solve this problem.

Given a string and $$$Q$$$ queries of the following kind, output the resulting string after all $$$Q$$$ queries have finished.

l r: reverse the substring in the interval $$$[l,r]$$$.

(This problem appeared on the Croatian Programming Contest 2010, you can try to solve it here.)

Now some of you might know a clear solution already — to use a splay tree. While other BBSTs can work with this type of queries, the splay tree would be one of the most well known ones. However, I do not know how to implement splay trees, but I do know that the rope exists. After a few hours of thinking, I came up with this solution.

Let us manage a rope $$$R$$$ with the given string $$$S$$$ and the reversed string $$$S'$$$ concatenated. If we denote the original length of the string as $$$N$$$, the new length of the string in the rope would be $$$2N$$$.

For all closed intervals $$$[l,r]$$$ representing a substring $$$s$$$, given that $$$1 \leq l \leq r \leq N$$$, we can also find a interval $$$[l',r']$$$ representing the reversed substring $$$s'$$$ in the same rope. And as clearly you may see, this interval $$$[l',r']$$$ corresponds to $$$[2N+1-r,2N+1-l]$$$. Now we can split the rope into five intervals based on these intervals we have found.

These five intervals I am speaking of are the two intervals we have (one from the query, one mirrored from that) and the three other intervals making up the rope. So the whole rope, represented by the five intervals, would be $$$[1,l)+[l,r]+(r,2N+1-r)+[2N+1-r,2N+1-l]+(2N+1-l,2N]$$$. Now we can swap the interval from the query with the mirrored interval. This new rope would be represented as $$$[1,l)+[2N+1-r,2N+1-l]+(r,2N+1-r)+[l,r]+(2N+1-l,2N]$$$, and would contain the new string and its mirrored one, concatenated. The time complexity for doing this operation would be $$$O(\log N)$$$, the same with the rope's time complexity.

Now for the output, we can save the result in a string and discard the latter half, as we do not need the reversed string now. The problem is solved.

The implementation of this solution is very simple, we can already use the functions given by the rope implementation (stated as "the most important" ones above). In my opinion, it is much simpler and easier to understand than implementing a splay tree. Last but not least, it also supports other operations possible on a rope (you can just mirror it on the reversed half as well). Thank you for reading, and as always, suggestions and questions are welcome.