Algorithm for counting specific type of inversions in an array

Question

I need an algorithm that counts the inversions of type: Inversion between a and b exists if a has lower index and a > 2b.

Can you think of an algorithm that would do it in O(n logn)?

Answer 1

It can be done via a small tweak in merge sort algorithm. Counting inversions in an array

In the normal standard algorithm during the merge phase you compare elements from left and right half and increase inversions by number of elements remaining in Left portion. Here we increment not by the number of elements remaining in the left half but rather by the number of elements remaining in the left half which are more than twice as large.