這題用樹狀數(shù)組比歸并排序快很多啊~~~
一個(gè)是500多一個(gè)2000多。
這題用樹狀數(shù)組，主要有兩點(diǎn)
I.離散化，把n個(gè)數(shù)映射到1-n里面，不然內(nèi)存不夠，
II.求一個(gè)數(shù)組的某一個(gè)數(shù)據(jù)的前面所有數(shù)據(jù)中比它小(或大)的所有數(shù)的個(gè)數(shù)
對(duì)于第一個(gè)，我們可以用一個(gè)struct，然后里面存兩個(gè)信息，一個(gè)是val，一個(gè)是no，其中val是輸入的數(shù)，no是用來離散化的。
對(duì)于第二個(gè)，很多人說是樹狀數(shù)組的基本功了，但是我覺得看怎么結(jié)束樹狀數(shù)組的。在這里你可以對(duì)每一個(gè)數(shù)update(a[i],1),然后再getsum(a[i])(a[i]是離散化后的數(shù)組)。這樣的話，你再用i - getsum(a[i])就是逆序數(shù)的對(duì)數(shù)了，如果不好理解的話，可以用5 2 1 4 3這個(gè)數(shù)組來模擬下。
對(duì)于這兩個(gè)問題解決了之后，這題就簡(jiǎn)單了
下面給出代碼(還是建議自己先想，不過離散化沒接觸的，可能會(huì)比較難想，樹狀數(shù)組還行吧)
CODE
1/**//*
2
ID:Klion
3 PROG:POJ_2299
4 LANG:C++
5 樹狀數(shù)組版
6 比歸并排序快多了~~~
7 注意兩點(diǎn)，I.離散化
8 II.樹狀數(shù)組求一個(gè)離散化后的數(shù)組里面的某一個(gè)數(shù)的前面的數(shù)據(jù)中
9 有多少個(gè)比它小的數(shù)
10
*/
11
#include<iostream>
12using namespace std;
13const int MAX = 500006;
14int tree[MAX];
15typedef struct
16
{
17 int val,no;//val是輸入的值，no表示是第幾個(gè)，用來離散化用
18}Node;
19Node num[MAX];//存輸入數(shù)據(jù)
20int aa[MAX];//存離散化之后的信息，離散化啊離散化
21int cmp(const void * a,const void * b)//離散化時(shí)用用到的排序模板
22{
23 return ((Node *)a)->val - ((Node *)b) ->val;
24}
25void update(int idx,int val)
26{//樹狀數(shù)組的更新
27 while(idx <= MAX)
28
{
29 tree[idx] += val;
30 idx += (idx & -idx);
31
}
32 return ;
33}
34int getsum(int idx)
35{//樹狀數(shù)組的求和
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個(gè)點(diǎ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 {//更新及計(jì)算結(jié)果
65 update(aa[i],1);
66 sum += (i - getsum(aa[i]));
67 }
68 printf("%I64d\n",sum);
69 }
70}
71