# CHEFINV - Editorial

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.

9 Likes

A better and shorter method to do it is using Fractional Cascading on Segment tree (to be precise merge sort tree).

4 Likes

I solve it by segment tree but i got wrong answer i generate random test case upto 2*10^5 and check it file input output but i could not get any test case where i was wrong
Can you please help me where my code fail  http://www.codechef.com/viewsolution/4823968

2 Likes

I used extended merge sort and segment tree for this where each of my query was logn^2 (4logn^2 to be precise). So overall solution was of MlgN^2 . This seems acceptable given 1 sec time limit. why I got tle???
http://www.codechef.com/viewsolution/4806941

Because MlogN was expected. That is the very reason why I used fractional cascading along with merge sort tree. Mergesort tree alone wouldnt do…

It was possible with a Fenwick tree I guess also. So you do two updates and get the new inversion count. Then discard the updates. Two updates would be to change A[x] to A[y] and A[y] to old A[x]. Then start fresh on new query.

what will be the complexity for that? and space requirements?

I have one (off topic) question.

To count the no. of inversion in array I am using BIT. This algorithm is well known and shown in this link

Suppose we have A={9,6,8,1000}. For this we need an array (say BIT) of length N, where N is the maximum number in array A (1000 here). But this algo requires the memory O(N). What what if A consist of very big number say 10^9. I am getting ‘java.lang.OutOfMemoryError’ while declaring BIT[10^9]. Is there any way to overcome with this?

map these to shorter range i.e. A= {9,6,8,1000} can be mapped to B={3,1,2,4}.
What you can do is sort A to get intermediate array = {6,8,9,1000} then map 6 to 1, 8 to 2, 9 to 3 and 1000 to 4 and then use this map and A to get B

3 Likes

@ajaytank try for compression thing try to compress the values in range of 2*10^5

Can segment tree work…I got wa with segment tree…??

@adijimmy I would be thankful to you if you post any link related to compress the values @ajaytank http://pavelsimo.blogspot.in/2012/09/counting-inversions-in-array-using-BIT.html
compression is explained in this link

1 Like

Fenwick Tree or Binary Indexed Tree are more useful in such cases and require less memory.They are easy to understand nad learn than segment tree also.

How much did you take for each query ?
I guess (might be wrong) I implemented a stupid cascading which gave 8*logn per query, if it was correct. But that solution timed out.

2 Likes

Did the same but probably that is why M, N = 2 * 10 ^ 5 because I tested it and it runs in appr. 1.6 s on my laptop, but 10^5 runs fine

I guess lower_bound and upper_bound are implemented as binary search algorithms. (important for maintaining complexity) You can at least decrease the factor of your queries by decreasing the size of your interval each time you search. Your algorithm fully binary searches the entire range 4 times, no matter what. But when you know a < b for example, the lower_bound of b can be found in the range[upper_bound(a),end]. The rest of your code looks pretty similar to mine. I wonder if that’s the only reason that yours TLE’d. I’m not using c++ very often so I guess the try is yours.

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).

Shouldn’t the top right corner be (X-1,max(ai))

1 Like

I think my query algorithm took 2*logn…

How do you use fractional cascading on segment tree to get a query time of 2*logn?
From what I’ve learned about fractional cascading it gives query time of (logn + k) where n is total number of elements in all lists and k is number of lists.
If you construct fractional cascading for all arrays in the merge sort segment tree, the number of lists would be n. So query time becomes order n.
If you construct fractional cascading for each query. That would itself take O(n) time.