PROBLEM LINK
Author: Sunny Aggarwal
Tester: Pushkar Mishra
Editorialist: Prateek Gupta
Russian Translator: Vitalij Kozhukhivskij
Vietnamese Translator: Khanh Xuan Nguyen
Mandarian Translator: Gedi Zheng
Contest Admin: Praveen Dhinwa and Pushkar Mishra
DIFFICULTY:
Hard
PREREQUISITES:
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 (j-i+1) towards the right. After each query, we have to report the inversion count in the new array.
NOTE:
- At the end of all queries, its not necessary that new array is completely filled with all N elements. Some positions may still be left vacant.
- It is also guaranteed that all the numbers inserted into the newly formed array will not go out of bounds i.e will occupy only first N indices, but may or may not be not all of them are occupied.
- It is strictly recommended to solve all the problems mentioned at the start of the editorial. Going through them will make it easier to understand the editorial of this problem.
An $\mathcal{O}(N\sqrt N\log N)$ Solution
The 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 re-arranged 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 ith element, we’ll find the Kth unoccupied index that has not been filled yet. Similarly, for any Pth 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:
Things are not finished yet. This is the last phase of the problem.
Now we have the final array, the answer to the last query will be the number of inversions in the final array. We start iterating queries from bottom to top here and keep removing the numbers for that specific query as we move up. Basically, we remove those numbers from the final array which are no longer required as they are inserted after this particular query. As we iterate the queries from bottom to top, we have to reduce the inversion count caused by the numbers inserted after this query.
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
- Complexity to calculate what all numbers first player will be inserting elements into the second player’s array will be \mathcal{O}(N\log N) as it takes \mathcal{O}(\log N) complexity for each element and there can be maximum N elements which he will remove.
- Complexity to calculate what all positions, first player will be inserting elements into the second player’s array will again be \mathcal{O}(N\log N) as it takes \mathcal{O}(\log N) complexity for each element and there can be maximum N elements which he will insert.
- Complexity to calculate inversions after the final array will be \mathcal{O}(N\log N).
- Complexity to calculate answer for each query while traversing from bottom to top will be \mathcal{O}(N\sqrt N\log N) as it takes \mathcal{O}(\sqrt N\log N) to calculate the removal impact of single element and we will ofcourse remove maximum N elements.
An $\mathcal{O}(N\log^2N)$ Solution
The 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 order-statistic operations in BBST, standard operations on BIT (including binary searching for the k^{th} set bit) and thorough understanding of Merge-sort tree and associated operations.
Algorithm
- Using one BIT, we can know the index in A of the element being inserted in B. To do this, we can initially add 1 to each index in the BIT. Then when a query (x, y) appears, we can binary search the BIT for x^{th} set bit to get the first element. We remove this bit and repeat binary searching x. We do this y-x+1 times.
- We can use a treap to insert the elements into right positions. At each node of the treap, we maintain the size of the subtree rooted at that node. This way we can find the positions where we need to insert the elements of a query (x, y). We start by finding position k, insert the first element, then find position k+1, insert the second element, and so on.
- Now We do an inorder traversal of the treap. This will give us how the array B looks after all the operations have been done.
- We can note that if a pair of numbers formed an inversion while the queries were being carried out, then that pair of numbers forms an inversion in the final B array too. So now we can use a segment tree with each node as a BIT to count the inversions. We insert the numbers one by one into the segment tree as per their final positions in B. The numbers are inserted in the same order that they were inserted in the treap.
- While inserting in the segment tree, we can count the inversions using the BIT at each node. We can print the count of the total number of inversions as and when required.
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).
Net complexity: \mathcal{O}(N\log^2N).