Count pairs (a,b) in two permutations such that index(a) < index(b) in both

Question

Given two permutations of (1, 2, 3,..N),

Consider for n = 5

5 4 3 2 1  
3 2 4 1 5  

Find number of pairs (a,b) such that index(a)<index(b) in both of the permutations?
In the above case, answer is 4.

(4,1) index(4)<index(1) in both permutations.
(3,1) 
(2,1)
(3,2)

We can easily do this in O(n²) but I feel like we can do this in O(nlogn). Can you please help?

Another example...

for n = 5

3 4 1 5 2 
1 3 2 5 4

Here answer is 5

(3,4) index(3)<index(4) in both perms.
(3,5) index(3)<index(5) in both perms.
(3,2)
(1,5)
(1,2)  

Answer 1

Yes, this can be solved in O(n log n) time in a quite elegant way. Since the numbers themselves don't really matter (just their indices), relabel them so that the first permutation is trivial; this takes O(n) time. The relabelling in the example is 1 → 3, 2 → 5, 3 → 1, 4 → 2, 5 → 4.

3 4 1 5 2 → 1 2 3 4 5 
1 3 2 5 4 → 3 1 5 4 2

Now index(a) < index(b) in the first permutation if and only if a < b, so we just need to count the number of pairs in the second permutation where a < b and index(a) < index(b), i.e. the number of pairs which are in the correct relative order. This is equal to (n choose 2) minus the number of inversions, which can be counted in O(n log n) time; see e.g. this other Stack Overflow Q&A.

Answer 2

This can be solved with order statistics rb tree.
Let's call the two arrays a, and b.(they are interchangeable)
Let their length be n.
We need the inverse permutation p of b. (that is: p[x] contains the index for the number x in b)
Let s be the set with order statistics.

We will store indices of already visited elements of b in s.
We iterate from i=0 to n-1 (let the arrays be zero indexed):
The number of elements after number a[i] in b is C = n-1 - p[a[i]].
Out of these, we need those elements, which did not appear in a yet. This can be calculated using s. We know the size of s, and in log(n) we can calculate the position of p[a[i]] in s. Subtract the number of elements that come after p[a[i]] in s from C, and add that to the answer.
At the end of each iteration, we add p[a[i]] to s.

Edit: If you use c++ with gcc compiler, such a set is already implemented, and used in competitive programming.

Answer 3

I would do it the following way. Lets use the example you gave:

3 4 1 5 2 
1 3 2 5 4

Keep a structure that (1) we can add a number to, and (2) given a number, can report how many numbers in the structure are greater (e.g., given 2, if the structure contained 1, 3, and 4, it would return 2).

Now iterate from right to left in the first permutation, A. For every number, A[i], after the first in the iteration, mark the previously visited number, A[i+1], by inserting in the structure that number's index in the second permutation. Then query the structure for how many elements in it are greater than the index of A[i] in B.

Back to our example:

indexes  0 1 2 3 4
A        3 4 1 5 2 
B        1 3 2 5 4

Iteration right to left on A:
2  skip

5  insert index of 2 in B
   structure: { 2 }
   query structure for how many are
   greater than index of 5 in B
   > 3: 0
   result: 0
   
1  insert 3 in structure
   structure: { 2, 3 }
   query > 0: 2
   result: 2
   
4  insert 0 in structure
   structure: { 0, 2, 3}
   query > 4: 0
   result: 2
   
3  insert 4 in structure
   structure: { 0, 2, 3, 4 }
   query > 1: 3
   result: 2 + 3 = 5