这题用树状数组比归并排序快很多啊~~~
一个是500多一个2000多。
这题用树状数组，主要有两点
I.离散化，把n个数映射到1-n里面，不然内存不够，
II.求一个数组的某一个数据的前面所有数据中比它小(或大)的所有数的个数
对于第一个，我们可以用一个struct，然后里面存两个信息，一个是val，一个是no，其中val是输入的数，no是用来离散化的。
对于第二个，很多人说是树状数组的基本功了，但是我觉得看怎么结束树状数组的。在这里你可以对每一个数update(a[i],1),然后再getsum(a[i])(a[i]是离散化后的数组)。这样的话，你再用i - getsum(a[i])就是逆序数的对数了，如果不好理解的话，可以用5 2 1 4 3这个数组来模拟下。
对于这两个问题解决了之后，这题就简单了
下面给出代码(还是建议自己先想，不过离散化没接触的，可能会比较难想，树状数组还行吧)
CODE
1/**//*
2
ID:Klion
3 PROG:POJ_2299
4 LANG:C++
5 树状数组版
6 比归并排序快多了~~~
7 注意两点，I.离散化
8 II.树状数组求一个离散化后的数组里面的某一个数的前面的数据中
9 有多少个比它小的数
10
*/
11
#include<iostream>
12using namespace std;
13const int MAX = 500006;
14int tree[MAX];
15typedef struct
16
{
17 int val,no;//val是输入的值，no表示是第几个，用来离散化用
18}Node;
19Node num[MAX];//存输入数据
20int aa[MAX];//存离散化之后的信息，离散化啊离散化
21int cmp(const void * a,const void * b)//离散化时用用到的排序模板
22{
23 return ((Node *)a)->val - ((Node *)b) ->val;
24}
25void update(int idx,int val)
26{//树状数组的更新
27 while(idx <= MAX)
28
{
29 tree[idx] += val;
30 idx += (idx & -idx);
31
}
32 return ;
33}
34int getsum(int idx)
35{//树状数组的求和
36 int ret = 0;
37 while(idx > 0)
38 {
39 ret += tree[idx];
40 idx -= (idx & -idx);
41 }
42 return ret;
43}
44int main(void)
45{
46 int n;
47 __int64 sum;
48 while((EOF != scanf("%d",&n)) && n)
49 {
50 for(int i = 1;i <= n;i++)
51 {
52 scanf("%d",&num[i].val);
53 num[i].no = i;
54 }
55 //用于离散化的排序
56 qsort(num+1,n,sizeof(num[0]),cmp);
57 for(int i = 1;i <= n;i++)
58 {//这里离散化，把n个点映射到1-n
59 aa[num[i].no] = i;
60 }
61 memset(tree,0,sizeof(tree));
62 sum = 0;
63 for(int i = 1;i <= n;i++)
64 {//更新及计算结果
65 update(aa[i],1);
66 sum += (i - getsum(aa[i]));
67 }
68 printf("%I64d\n",sum);
69 }
70}
71