题目描述
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 — the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
题目链接
http://poj.org/problem?id=2299
解题思路
一道比较简单的题，就是求逆序数。有树状数组和归并排序两种解法，下面给出了树状数组的解法，树状数组这次用结构体搞的。
AC代码
11324K/625MS/G++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
typedef long long ll;
using namespace std;
struct Number
{
ll num;
int index;
} num[500005];
bool cmp(const Number a, const Number b)
{
return a.num > b.num;
}
int N;
ll bit[500005];
int lowbit(int x)
{
return x & (-x);
}
void update(int i, int delta)
{
for (int j = i; j <= N; j += lowbit(j))
{
bit[j] += delta;
}
}
ll sum(int k)
{
ll cnt = 0;
for (int i = k; i > 0; i -= lowbit(i))
{
cnt += bit[i];
}
return cnt;
}
int main()
{
ll cnt = 0;
while (~scanf("%d", &N) && N)
{
memset(bit, 0, sizeof(bit));
cnt = 0;
for (int i = 1; i <= N; i++)
{
scanf("%I64d", &num[i].num);
num[i].index = i;
}
sort(num + 1, num + 1 + N, cmp);
for (int i = 1; i <= N; i++)
{
cnt += sum(num[i].index);
update(num[i].index, 1);
}
printf("%I64d\n", cnt);
}
return 0;
}