PROBLEM LINKAuthor: Sunny Aggarwal DIFFICULTY:HardPREREQUISITES:Data Structures, Binary Indexed Trees/Segment trees, Balanced Binary search Trees, Binary Search, Square root Decomposition RECOMMENDED PROBLEMS:PROBLEM:Given an array and number of queries. All the queries will insert a contiguous subarray at a particular position into a new array which was initially empty. Each query is of the form $K$ $i$ $j$, which denotes elements with indexes from range $i$ to $j$ of given array are inserted into new array at an index $K$. All the elements which were present in the new array at pos ≥ $K$ get shifted by a distance of $(ji+1)$ towards the right. After each query, we have to report the inversion count in the new array.NOTE:
An $\mathcal{O}(N\sqrt N\log N)$ SolutionThe problem can be split into number of different parts. We will break this problem down into parts and then arrive at the final solution. Finding elements to be inserted for each query The first and foremost priority is to keep track of what all set of numbers first player would be inserting into second player's array for each query. This is important as the original array gets rearranged after some contiguous subarray is removed from it to fill in the removed elements. This can be implemented either by segment tree or binary indexed tree in $\mathcal{O}(\log N)$.The next good thing to do is to compute the final array after the game has finished. That way we can move from bottom to top and answer each query offline. Computing the final array after all $Q$ operations have been performed: It seems quite complex initially to form the array after each single move of the first player. Instead, lets store all the queries and start iterating them bottom to top. So, while traversing the queries and starting to place each element in the empty array of second player, we are basically trying to decide its index for each query in $\mathcal{O}(\log N)$ and we will have to place maximum $N$ elements in all, amounting to $\mathcal{O}(N\log N)$ complexity. So, while traversing backwards, lets say we encounter a query of the form $K$ $i$ $j$, meaning we have to place the elements from range($i$,$j$) of the first array into the new array starting from index $K$. We have already kept track of the elements that are going to be inserted in new array for each query. For $i$^{$th$} element, we'll find the $K$^{$th$} unoccupied index that has not been filled yet. Similarly, for any $P$^{$th$} element in range($i$,$j$), we'll find the $(K+P)$^{$th$} unoccupied index and place each element within the range into the second player's array manually. Processing each query offline: This can be implemented by square root decomposition. Here, we divide our new array into $\sqrt N$ blocks. We keep a binary indexed tree at each block and update the value of that particular element if it falls in that particular block. for eg: update(block_idx_, val, 1). Now, If we remove a specific number from a specific block. we have to reduce the number of inversion which were counted due to this element. For this, we need to count how many elements are there in the array having value greater than this element and are present before it in the same block or in its left blocks. Similarly, count the elements having value lesser than this element and are present after it in the same block or in its right blocks. And then, we remove this element from the array and it will not be included further. This can be done by iterating that particular block in $\mathcal{O}(\sqrt N)$. There can be max $\sqrt N$ blocks and for each block, query using the BIT will take $\mathcal{O}(\log N)$ time. Overall to remove all the elements from the first array and henceforth calculating the new inversion count would take $\mathcal{O}(N\sqrt N\log N)$ complexity. COMPLEXITY
An $\mathcal{O}(N\log^2N)$ SolutionThe problem can be solved in $\mathcal{O}(N\log^2N)$ using Binary Indexed Trees (BIT), Segment Tree and a Balanced Binary Search Tree (BBST). Tester's solution uses this approach with Treap as the BBST. The method answer queries in offline manner. The explanation given below assumes that the reader has good understanding of orderstatistic operations in BBST, standard operations on BIT (including binary searching for the $k^{th}$ set bit) and thorough understanding of Mergesort tree and associated operations. Algorithm
Complexity Binary searching on BIT is $\mathcal{O}(N\log^2N)$. Inserting in treap is $\mathcal{O}(N\log N)$. Doing BIT operations for each of the $\log N$ nodes of the segment tree that we visit while inserting into segment tree is further $\mathcal{O}(N\log^2N)$. SOLUTIONS
This question is marked "community wiki".
asked 26 Aug '15, 01:24

Is there any tutorial for sqrtdecomposition in Codechef? answered 30 Aug '15, 17:15

You don't have to use a Treap for the second part of the solution. You can achieve O(n log^2(n)) complexity by having a simple segment tree which keeps a sorted segment [b, e] at each node. When you insert an element, you binary search for the value and "add" to a BIT at the node at the found position. Then you have to update the inversions, which can be done in O(log^2(n)) by: delta(Inv[node]) = delta(Inv[node2]) + count(node2+1, [value+1...INF]) if value belongs in the left subtree or: delta(Inv[node]) = delta(Inv[node2+1]) + count(node2, [0...value1]) if value belongs in the right subtree. To see what I mean, take a look at my solution (try to ignore the Treap part, that is just to find the right positions to insert the numbers). Complexity is O(n log(n)) (first part) + O(n log^2(n)) (second part) https://www.codechef.com/viewsolution/7959515 Note: Not sure how this is a junior problem, though it teaches nice techniques :). answered 30 Aug '15, 20:40
I (tester) havent used treaps in the second part. Second part is just segment tree and BITs.
(31 Aug '15, 10:44)

Computing the final indices in array B can be done by using answered 04 May '16, 19:27
