Let
A[0...n – 1] be an array of n
distinct positive integers. If i <
j and A[i] > A[j] then the
pair (i, j) is called an inversion of A. Given n and an array A your task is
to find the number of inversions of A.
Input. The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n
≤ 200000). Then n + 1 lines
follow. In the ith line a number A[i
– 1] is given (A[i – 1] ≤ 107).
The (n + 1)th line is a blank space.
Output. For every test output one line giving the number of
inversions of A.
|
Sample Input |
Sample Output |
|
2 3 3 1 2 5 2 3 8 6 1 |
2 5 |
сортировка
При помощи сортировки слиянием
вычисляем количество инверсий за O(n
logn).
Реализация
алгоритма
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX
200010
using namespace std;
int m[MAX];
int
tests, n, i, j;
long long swaps;
void
merge(int *a, int
bleft, int bright, int
cleft, int cright)
{
// a[bleft..bright]
-> res[]
// res[0..len-1]
a[cleft..cright] are merged into a[bleft..cright]
// we copy only
half of array
int i, len =
bright - bleft + 1, resCur = 0;
int *res = new int[len];
memcpy(res,a + bleft,len*sizeof(int));
while((resCur
< len) && (cleft <= cright))
{
if
(res[resCur] <= a[cleft]) a[bleft++] = res[resCur++];
else
a[bleft++] = a[cleft++], swaps += len - resCur;
}
while (resCur
< len) a[bleft++] = res[resCur++];
delete[] res;
}
void
mergeSort(int *a, int
left, int right)
{
if (left
>= right) return;
int middle =
(left + right) / 2;
mergeSort(a,left,middle);
mergeSort(a,middle+1,right);
merge(a, left, middle, middle + 1, right);
}
int main(void)
{
scanf("%d",&tests);
while(tests--)
{
scanf("%d",&n);
for(swaps =
i = 0; i < n; i++) scanf("%d",&m[i]);
mergeSort(m, 0, n - 1);
printf("%lld\n",swaps);
}
return 0;
}