POJ2299 UltraQuickSort解题报告（树状数组+离散化模板）

　　　　　　http://poj.org/problem?id=2299

　　　　　　题意：多组数据测试，给一个n和一个长度为n的序列，求此序列的逆序数；

　　　　 初学树状数组，理解其结构和功能（可查询前缀和），离散化一下，树状数组计数即可，详见代码及注释。

　　　　 外加离散化实现模拟。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define maxn 501000
 5 
 6 using namespace std;
 7 
 8 struct NUNO
 9 {
10     int w,pos;
11 }v[maxn];
12 
13 int n;
14 int a[maxn];
15 int tr[maxn];
16 
17 bool cmp(NUNO a,NUNO b)
18 {
19     return a.w<b.w;
20 }
21 
22 int low_bit(int x)
23 {
24     return x&(-x);
25 }
26 
27 void update(int i,int v)
28 {
29     while(i<=n)
30     {
31         tr[i]+=v;
32         i+=low_bit(i);
33     }
34 }
35 
36 long long get_sum(int x)
37 {
38     long long s=0;
39     while(x>=1)
40     {
41         s+=tr[x];
42         x-=low_bit(x);
43     }
44     return s;
45 }
46 
47 
48 int main()
49 {
50     ios::sync_with_stdio(0);
51     cin.tie(0);
52     cout.tie(0);
53 
54     //离散化
55     /*
56 
57         例子：
58     i    1 2 3        1 2 3
59     v.w  9 8 7        7 8 9         i    1 2 3
60   v.pos  1 2 3----->  3 2 1---->   a[i]  3 2 1
61 
62     */
63     while(cin>>n,n){
64     for(int i=1;i<=n;i++)
65     {
66         cin>>v[i].w;
67         v[i].pos=i;
68     }
69 
70     sort(v+1,v+n+1,cmp);
71 
72     for(int i=1;i<=n;i++)
73     {
74         a[v[i].pos]=i;
75     }
76 
77 
78     memset(tr,0,sizeof(tr));//无数据存在于数组 全标记为0
79 
80     long long ans=0;
81     //大于a[i]的元素个数=总元素个数-小于等于a[i]的元素个数
82 
83     for(int i=1;i<=n;i++)
84     {
85 
86         update(a[i],1);//将a[i]加入数组 将其标记为1 则包含a[i]的前缀和均+1
87 
88         ans+=(i-get_sum(a[i]));//get_sum()得到的是小于等于a[i]的元素数目
89 
90         //若再插入的a[i+1]>=a[i] 则a[i+1]的前缀和为1 说明小于等于a[i+1]的元素已经存在一个了
91     }
92     
93     cout<<ans<<endl;
94     }
95 
96 
97     return 0;
98 }