I found this problem on the problem set of a contest in some training camp, but couldn't find more information beyond that. The problem statement is as follows:
Consider n different urns and $$$n$$$ different balls. Initially, there is one ball in each urn.
There is a special device designed to move the balls. Using this device is simple. First, you choose some range of consecutive urns. The device then lifts all the balls from these urns. After that, you specify the destination which is another range of urns having the same length. The device then moves the lifted balls and places them in the destination urns. Each urn can contain any number of balls.
Given a sequence of movements for this device, find where will each of the balls be placed after all these movements.
The first line contains two integers $$$n$$$ and $$$m$$$, the number of urns and the number of movements $$$(1 \leq n \leq 100 000,1 \leq m \leq 50 000)$$$.
Each of the next $$$m$$$ lines contain three integers count $$$i , from_i$$$ and $$$to_i$$$ which mean that the device simultaneously moves all balls from urn $$$from_i$$$ to urn $$$to_i$$$ , all balls from $$$from_{i + 1}$$$ to urn $$$to_{i + 1}$$$, . . ., all balls from urn $$$from_i + count_i − 1$$$ to urn $$$to_i + count_i − 1 (1 \leq count_i , from_i , to_i \leq n, \max(from_i , to_i ) + count_i \leq n + 1)$$$.
Could anyone please give a hint? Thanks in advance!
Store the positions of all the balls in a treap. Simulate the lifting of the balls by split operations. Simulate the moving by lazy propagation. Simulate dropping the balls by merging back into the original treap.
Time complexity: $$$O((n+q)\log^2{n})$$$.
To bound the runtime, consider the potential function of sums of logarithms of differences between adjacent distinct values.
I wonder if splay trees will be faster.
Can you explain a little more about the time complexity part?
I will assume you are familiar with amortized analysis.
The potential function will be the sum of logarithms of differences between adjacent distinct values in all treaps. If there are a total of $$$n$$$ values stored in the treaps, and all of them are always between $$$0$$$ and $$$C$$$, the potential is bounded by $$$O(n\log{C})$$$. Also, splitting a treap and adding a constant to all values in a treap clearly will not increase the potential.
When we merge two treaps, we will switch between taking values from the first treap and from the second treap. Let $$$k$$$ be the number of switches. The actual cost of merging two treaps is $$$O(k\log{n})$$$. For conciseness, we will charge $$$k$$$ to the potential decrease and multiply back $$$\log{n}$$$ at the end.
Let $$$a_1,a_2,\ldots,a_k$$$ be the differences between adjacent elements that came from different treaps. The change in potential is at most
Since $$$\log(x+y)\ge \frac{1}{2}\log x+\frac{1}{2}\log y+\log 2$$$, the above expression is at most
Thus, the amortized cost of merging is $$$O(\log{n}\log{C})$$$. Duplicate values can be handled by adding the number of distinct elements in each treap to the potential.
In this problem, $$$n=C$$$, so the time complexity is $$$O((n+q)\log^2 n)$$$.
If we consider the process backwards, the problem becomes quite easy. Let's have a treap where in $$$x$$$-th node we will store where it will end up.
Then when we consider the operations in reverse order this will be equivalent to setting the values in the interval $$$[from_i, from_i+count_i-1]$$$ to $$$[to_i, to_i+count_i-1]$$$. In other words we need to copy an interval and paste it somewhere.
This can be done with any persistent BST by doing a couple of merges and splits. The time complexity will be $$$O(n \log n)$$$. Persistent AVL will definitely pass without problem for such constraints but you can also use treap with rebuilding it when the maximum depth becomes large.
Your solution work if condition $$$max(from_i, to_i) \geq min(from_i, to_i) + count_i$$$ true for all queries
Why won't it work if that's not the case?
PS: The problem OP was refering was at Pre-Finals Workshop 2018 and the official solution is the one I explained.