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].
给定N (1 <= N <= 65537 )个整数A1, A2, ..., AN (0 <= Ai <= 10^9)。你需要计算满足1 <= i < j <= N且A[i] > A[j]的数对(i, j)的总数。
The first line of the input contains the number N. The second line contains N numbers A1...AN.
输入的第一行包含整数N。第二行包含N个整数A1, A2, ..., AN。
Write amount of such pairs.
输出满足条件的数对的个数。
5
2 3 1 5 4
3
逆序数。树状数组即可。每次更新A[i]为1，然后所有的逆序数就是A[i] - Sum(A[i] - 1) + 1，更新的同时获取答案。
注意答案可能会超int，所以使用long long。
数据中A[i]的值过大，但是N最大只有65537，所以使用离散化即可，离散化只要sort一下，然后用lower_bound即可。
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
const int MAX = 102400;
int N;
int T[MAX], A[MAX], B[MAX];
int LowBit(int x);
void Update(int x, int y);
long long Sum(int x);
int main()
{
while(cin >> N)
{
long long ans = 0;
memset(T, 0, sizeof(T));
for(int i = 1; i <= N; i++)
{
cin >> A[i];
B[i] = A[i];
}
sort(B + 1, B + N + 1);
for(int i = 1; i <= N; i++)
{ A[i] = lower_bound(B + 1, B + N + 1, A[i]) - B; }
for(int i = 1; i <= N; i++)
{
Update(A[i], 1);
ans += A[i] - Sum(A[i] - 1) - 1;
}
cout << ans << endl;
}
return 0;
}
int LowBit(int x)
{ return x & (-x); }
void Update(int x, int y)
{
while(x <= N)
{
T[x] += y;
x += LowBit(x);
}
}
long long Sum(int x)
{
long long ans = 0;
while(x)
{
ans += T[x];
x -= LowBit(x);
}
return ans;
}
最近整理了一下树状数组，准备刷一下树状数组专题，这道题目是非常基础的应用。
原文：http://www.cnblogs.com/Ivy-End/p/4295101.html