180. Inversions
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
memory limit per test: 4096 KB
input: standard
output: standard
output: standard
There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<=i<j<=N and A[i]>A[j].
Input
The first line of the input contains the number N. The second line contains N numbers A1...AN.
Output
Write amount of such pairs.
Sample test(s)
Input
5
2 3 1 5 4
2 3 1 5 4
Output
3
离散化+树状数组
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 70000;
__int64 bintree[N];
int xis[N];
int arr[N];
int cnt;
int lowbit(int x)
{
return x & (-x);
}
void add(int x)
{
for (int i = x; i <= cnt; i += lowbit(i))
{
bintree[i]++;
}
}
int sum(int x)
{
__int64 ans = 0;
for (int i = x; i; i -= lowbit(i))
{
ans += bintree[i];
}
return ans;
}
int binserach(int x)
{
int l = 1, r = cnt, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (xis[mid] > x)
{
r = mid - 1;
}
else if (xis[mid] < x)
{
l = mid + 1;
}
else
{
return mid;
}
}
}
int main()
{
int n;
while (~scanf("%d", &n))
{
memset (bintree, 0, sizeof(bintree));
cnt = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%d", &arr[i]);
xis[++cnt] = arr[i];
}
sort (xis + 1, xis + cnt + 1);
cnt = unique(xis + 1, xis + 1 + cnt) - xis - 1;
__int64 ans = 0;
for (int i = 1; i <= n; ++i)
{
int cur = binserach(arr[i]);
add(cur);
ans += i - sum(cur);
}
printf("%I64d\n", ans);
}
return 0;
}