Problem link : contest practice
Difficulty : Medium
Pre-requisites : Fenwick tree
Solution:
Unlike the version when we swap the elements permamently, this one has an O(M log N) solution. The simplest solution is the offline one. That means that we’ll first read all the queries at once, then we’ll do something and then we’ll output all the answers at once. The online solution is also possible, and it involves persistent data structures.
At first we need to calculate the number of inversions in the initial array.
Consider the situation when we have to swap two elements of the array, say the L-th and the R-th one. In order to deal with such a query, we will act in two steps:
- First, we will decrease the number of inversions by the number of inversions that has the L-th element of the initial array. Then, we will decrease the number of inversions by the number of inversions that has the R-th element of the initial array. Note that if the pair (L, R) forms the inversion then it will be considered twice. So, we need to handle this case;
- Second, we can swap the L-th and the R-th elements and then add the number of inversions that contain these elements.
So now, the problem is to count the number of inversions that contain some exact element. Let it be the X-th element. This number will be equal to the amount of the numbers that has indexes that are smaller than X but are greater than aX plus the amount of numbers that has indexes greater than X but are smaller than aX. Here we denote the X-th element of the array by aX.
How to do it quickly? We can reduce this problem to another one. Consider a set of N points on a plane. Let the coordinates of the i-th point be (i, ai). Then, the amount of
numbers that has smaller indexes than X and are greater than aX equals to the number of points in the axes-parallel rectangle with the following bottom-left and top-right corners: (1, aX+1) and (X-1, N). Similarly, the amount of numbers that has indexes that are greater than X and are smaller than aX is the amount of points in the axes-parallel rectangle with the following corner points: (X+1, 1) and (N, aX-1).
How to calculate the number of points inside of the rectangle fast?
Here is the offline approach key points:
- The amount of points in the axes-parallel rectangle with the bottom-left and top-right points with the coordinates (x1, y1) and (x2, y2) respectively (let’s call it F(x1, y1, x2, y2)) equals to F(1, 1, x2, y2)-F(1, 1, x1-1, y2)-F(1, 1, x2, y1-1)+F(1, 1, x1-1, y1-1), so now we can operate only in rectangles that has (1, 1) as the bottom-left corner.
- Since we always have the bottom-left corner equal to (1, 1), we can iterate through all the possible X-coordinates and add all the points that has the current X-coordinate - there will be only one point for each X-coordinate, in fact. By add we mean adding the point’s Y-coordinate in the Fenwick tree. Then, before we add the points with the greater X-coordinates, we can answer all the queries that has this X-coordinate and the X-coordinate of the top-right corner. For the reasons, similar to the described above, the answer will be equal to some prefix-sum in the fenwick tree.
The complexity of above solution is O(N log N).
But there is also an online solution that has the same complexity. The key idea is the same, but we count the amount of points inside the rectangles in the different way. Here you can find a very comprehensive tutorial, related to calculation the number of points inside axes-parallel rectangle in O(log N) time on-line.
Setter’s solution: link
Tester’s solution: link
