Given two permutations of n, find a pair of indices such that... So if you are given two permutations of n (A and B), find a pair of indices i, j such that A[i] > A[j] and B[i] < B[j].
For example, consider two permutations A = (5, 7, 2, 1, 4, 6, 3) and
B = (6, 7, 4, 3, 1, 5, 2). In the first list A[4] = 1 < A[7] = 3, but in the second list B[4] = 3 > B[7] = 2.
Thus, the algorithm can return the pair (4, 7) of indices.
I have to give an algorithm to solve such a problem above. The hint is to show that you can assume without loss of generality that for all i, A[i] =/= B[i].
Obviously, the naive brute force way would work but I am looking for the algorithm that runs with the best possible running time.
Any help would be appreciated!
 A: An $O(n\log n)$ algorithm exists.
Sort array $A$, and reorder $B$ such that the original pair $A[i]$ and $B[i]$ are located at $A[\sigma(i)]$, $B[\sigma(i)]$, where $\sigma$ is a permutation of $i$ which sorts $A$.
The number of pairs $(i,j)$ is preserved as these get mapped to the pairs $(\sigma(i),\sigma(j))$. Hence, we can assume $A$ is sorted in increasing order.
A Fenwick Tree is a data structure which supports 2 queries efficiently, range sum and point update. We will be using this extensively.
For $A[i]>A[j]$, we need $i>j$ since $A$ is sorted.
Initialise a Fenwick tree which is of length $n$, with zeroes.
We linear scan through $B$, where for each element in $B$, we store the fact that the current value is stored at the current position.
For each element $x$ from $1$ to $n$ in the array $B$, we can get the position of $x$, which we call $j$. Update the Fenwick tree at that position to $1$. As all the other elements we have updated in the Fenwick tree are smaller than it, we need to count the number of $1$'s there are behind $j$ (since $i>j$, as established earlier). This is a range query from position $j+1$ to $n$ on the Fenwick tree. This efficiently counts the number of pairs where $B[j]$ is the bigger number.
