Hello, I am solving sqrt decomposition questions. I saw this question on the list but I am unable to understand how to solve this. I read the editorial but still confused. Please help in solving this question. Do tell if you recommend solving some other types of questions before solving this one.
Thank you
Problem link?
Added Link.
The implementation is difficult, but it’s doable.
Firstly break it into blocks like you normally do. For each hole in the block calculate the number of steps to reach into the next block = steps[i], which elements in this block lead directly to this hole =prev[i] , and which element of the next block you reach =next[i].
There are \sqrt{n} blocks and you should be able to do it for each block in O(n) even if you just brute force each hole. You can also do it in O(\sqrt{n}), because it’s a DAG.
Then for update queries, first update the prev[i] which contains this, and put it in the correct one. Also recalculate where it will go. That can be done in O(1) or O(\sqrt{n}), doesn’t really matter.
Do a reverse BFS using the information of which holes lead directly to this and update them accordingly (Same value but add distance to steps). Remember there are only \sqrt{n} elements at most. This won’t affect the previous block because next is the immediate first element in the next block.
For jump queries, jump from block to block, adding the distance needed, which we have saved for each hole already, so we will have \sqrt{n} jumps.
We will calculate everything per block so that during update time we can avoid updating whole arrays with size n.
Now,we can update only at most sqrt(n) of a particular elements per update.
And per query it takes sqrt(n) time complexity
because we have to visit at most sqrt(n) blocks
The solution is bit a classical implementation of sqrt decomposition
Here is my solution with well comments line if you need
