I participated in a programming contest in which I was unable to solve a problem, the problem was:
Given an array A of n integers, I need to count the number of inversions in given ranges. An integer m is provided which tells the number of ranges, then m lines follow, in each line two integers li and ri are given.
We have to count inversions in specified range only i.e. from li to ri inclusive(0 based indexing).
Two elements A[i] and A[j] add to inversion if A[i]>A[j]
and i<j
.
for example: A=[3 2 1 4]
The inversions are:
(2, 1), (3, 1), (3, 2) i.e. total number of inversions are 3.
Input:
3 2 1 4 //Array A
3 // m - no. of ranges
1 2 // range
2 3
0 3
Output:
1
0
3
Constraints:
n<=2*10^4
m<=2*10^4
A[i]<=10^9
I know methods to compute inversion count in O(nlogn) (such as BIT or merge sort) on whole array and if I apply same here to every range the complexity would be O(mnlogn), that's surely not acceptable as time limit is 1 second.