這題用樹狀數組比歸并排序快很多啊~~~
一個是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