I solved it via euristic with O(M*SqrtN) solution. To do that required split initial array by batched with size SqrtN for 10^5 it will be 316. Hence we have 316 batches with size 316 inside each. After that you need simulate both type of operations. To handle each query required SqrtN operations, but after each query size of batches maybe increased by 2. To avoid growing of count of batches required rebuild all array every SqrtN operations.

What we have: 1) Required rebuild all array M / SqrtN times with O(N) complexity it will be O(M * SqrtN) 2) Each query will take SqrtN operation and it is required to run M times, it will be O(M * SqrtN).

As result we have O(M * SqrtN) complexity.

I solved this problem without using any sort of tree. I'm doing inverse mapping from the last transform to the first one, where I rasterize inverse transforms in chunks. The key for improving performance is to use a cache for nearby sample points so that we don't have to do a full recursion if the cache is still valid (at some recursion level). The cache point can be saved for each transform, but it is essential that we rasterize from 1 to N in each chunk in order to take full advantage of the cache.

Can someone tell me is the explanation of ARRAY AND SIMPLE QUERIES explanation given is right when entered 2 3 5 the array doesnot change the position of 3, but rest every thing is changed. Help me with it . hence my code is not submitting. I am actually getting the right answer as per the question. But i feel the explantion and the expected output is wrong in the question itslef and also the test cases. can anyone expalin it to me.

Could someone help me with the right approach here? I took a look at splay-trees and they don't seem to quite fit. Anyone got a different approach?

This problem took me longer than I had hoped to solve, basically because a lot of the write-ups are not necessarily clear on a few points. To solve this you need to use a Treap with implicit indexing. Various comments below have cited resources for learning about a Treap and how to implement it, the challenge for me was implicit indexing.

In my initial solution I created a Treap using a key, value pair, where the key was the index of the array (zero based), and the value was whatever value was at that index. I then implemented a lookup method based upon the key, so for instance I could look up at index five and get whatever the value was. When I implemented implicit indexing I had an incorrect understanding of what was an implicit index. When you split a tree with implicit indexes you do it based upon sub-tree sizes, in this case the size of the left sub-tree. When I was doing the split I was passing in the key, not the implicit index. Consider the following example:

{ 1, 2, 3, 4, 5, 6, 7, 8 }

For this problem if you implement a query of “1 2 4” that means you want to take values { 2, 3, 4 } and put them at the front of the array, giving you:

{ 2, 3, 4, 1, 5, 6, 7, 8 }

Now you have a second query of “2 3 5.” My initial misunderstanding was that given I needed to split based upon the second position in the array, I would look up the key at value “3” and then use it. That’s wrong. For implicit indexing you don’t do that at all, because your tree is in a state that you may not find the key as it could be out of order. With implicit indexing you assume that risk, and instead simply pass in the index of where you want to split. So instead of whatever the key was at value three, I instead just said split based upon a key of one (zero based indexing, so 2-1 is 1), as we want the following result:

Left tree = { 2, 3 }

Right tree = { 4, 1, 5, 6, 7, 8 }

With the above we are now set to do another split, this time at position two. That is calculated by taking the end value of five, minus the start value of three, giving us the position of two (again, zero based) that we want to do the split off of. The result there is:

Unchanged left tree = { 2, 3 }

Middle tree = { 4, 1, 5 }

Right tree = { 6, 7, 8 }

That was the breakthrough moment, once I understood that with implicit indexing keys don’t matter, and it really is relative to position, everything else made sense.

I got a 100% completion rate for my solution that used C#. I’ve cleaned up my code, made a bunch of comments, and created a GitHub repository so that others can read my solution and learn from it. Once you understand how it works this really is a useful concept and I’m glad I did it. But a lot of the write-ups on this are heavy in academia and lacking in practical walkthroughs, save for the following YouTube video: https://youtu.be/erKlLEXLKyY, which gave a reasonable explanation of things, but glossed over the fact an implicit index really is just the index, and not a key.

C# solution built using Visual Studio 2017 Community edition can be found at https://github.com/MrAngry52/Treap.