Counting inversion after swapping two elements of array

Question

You are given a permutation p1,p2,...,pn of numbers from 1 to n.

A permutation is a sequence of integers from 1 to n of length n containing each number exactly once.

You are given q queries where each query consists of two integers a and b, In response to each query you need to return a number of inversions of permutation after swapping elements at index a and b, Here every query is independent i.e. after each query the permutation is restored to its initial state.

An inversion in a permutation p is a pair of indices (i, j) such that i > j and pi < pj. For example, a permutation [4, 1, 3, 2] contains 4 inversions: (2, 1), (3, 1), (4, 1), (4, 3).

Input: The first line contains n,q. The second line contains the space-separated permutation p1,p2,...,pn. Each line of the next q lines contains two integers a,b.

Output: For each query Print an integer denoting the number of Inversion on a new line.

Sample input: 
5 5
1 2 3 4 5
1 2
1 3
2 5
2 4
3 3

Output: 
1
3
5
3
0

Constraints: 
2<=n<=1000
1<=q<=200000

My approach: I am counting no of inversions using BIT (https://www.geeksforgeeks.org/count-inversions-array-set-3-using-bit/) for each query after swapping elements at position a and b..and then again swapping it so that my array remains unchanged. But this solution gives TLE for large test cases. Is there any better approach for this problem?

Answer 1

We can solve this in O(n log n) space and O(n log n + Q * log^2(n)) time with a merge-sort tree. The merge-sort tree allows us to find the number of elements inside a subarray that are greater than or lower than an input number in O(log^2(n)) time and O(n log n) space.

First we record the total number of inversions in O(n log n) time, for which there are known methods. To query the effect of a swap bound by left and right, consider the subarray between:

subtract the number of elements greater
than right in the subarray (those will
no longer be inversions)

subtract the number of elements smaller
than left in the subarray (those will
no longer be inversions)

add the number of elements greater
than left in the subarray (those will
be new inversions)

add the number of elements smaller
than right in the subarray (those will
be new inversions)

if right > left, add 1
if left > right, subtract 1

Answer 2

You are getting TLE probably because number of computations in this approach is q * (n * log(n)) = 2 * 10^5 * 10^3 * log(1000) = ~10^9, which is more than generally accepted computations ~10^8.

I can think of the following solution. Please note that I have not coded / verified it:

• Denoting r_i == number of indices j, such that i > j && pi < pj. Eg: [2, 3, 1, 4], r₃ = 2. Basically, it means the number of inversions with the farther index as i. (Please note that I am using 1-based index as per the question. Also,a < b as per the question)

• Thus we have: Sum of r_i == #invs (number of inversions)

• We can calculate initial total #invs in O(n^2)

• When a and b are swapped, we can observe that:

  a) r_i remains constant, where i < a .

  b) r_i remains constant, where i > b.

• Only r_i changes where a <= i <=b, and that too on these following conditions. I am considering the case when pa < pb. Exact opposite case will need to considered when pa > pb.

  a) Since pa < pb, thus this swap causes #invs = #invs + 1

  b) If (pi < pa && pi < pb) || (pi > pa && pi > pb), this swap does not change r_i. Eg: [2,....10,....5]. Here Swapping 2 and 5 does not change the r value for 10.

  c) If pa < pi < pb, it will increment r_i by 1, and new r_b by 1. Eg: [2,....3,.....4], when 2 and 4 are swapped, we have [4,....3,....2], the rvalue 3 increases by 1 (because of 4); and also the r value of 2 increase by 1 (because of 3). Please note that increment because of what about 4 > 2? was already calculated in step (a), and needs to be done once only.

  d) We need to find all such indicies i where pa < pi < pb as we started with above. Let us call it f(a, b). Then the total change in #invs delta = (2 * f(a, b)) + 1, and answer will be #original_invs + delta.

As I mentioned, all the exact opposite steps need to be done for the case pa > pb. The delta will be negative in that case.

Now, the only thing remained is to solve: Given a, b, find f(a, b) efficiently. For this, we can pre-process and store it for all pairs of indices. This will take O(N^2) space, and O(N^2 * log(N)) time, using a balanced binary-search-tree (BST). Again showing steps for pre-processing for case pa < pb only. Another set of pre-processing steps needs to be done for the other case:

• We will use self-balancing BST, in which each node also contains the following fields:

  a) field_1: This denotes the size of the left sub-tree. This value will be updated on every insert operation, if size of left-sub-tree changes.

  b) field_2: This denotes the number of elements < node.value that this tree has. This value is initialized once when the node is inserted and does not change thereafter. I have added a small explanation of how it will be achieved in Addendum-A. This field is basically our pre-processing, which will determine f(a, b).

• With all of this now, for each index i, where 0 <= i < n, do the following: Create new tree. Insert pj values into the tree one by one, where (i < j < n ) && (pa < pj) . (Please note we are not inserting values where pa > pj). The method given in Addendum-A will make sure we find f(i, j) while inserting.

There will be n such pre-processed trees, one for every index. For finding f(a, b): We need to look into a^th tree, and search node.value = pb. This node's field_2 = f(a, b).

The complexity of insertion is O(logN). So, the total pre-processing computation = O(N * N(logN)). Search is O(logN), so the query complexity is O(q * logN). Total complexity = O(N^2) + O(N * N (logN)) + O(q * logN) which will turn out ~10^7

==============================================================================

Addendum A: How to populate field_2 while inserting node:

     i) Insert the node, and balance the tree. Update field_1 as required.

     i) Initailze ans = 0. Traverse the BST from root searching for your node. 

     iii) do { 
               If node.value < search_key_b, ans += node.left_subtree_size + 1
         } while(!node.found)
     iv) ans -= 1