poj 2299 Ultra-QuickSort (树状数组求逆序数）

 1 /*********************************************
 2 题目：    Ultra-QuickSort（poj 2299）
 3 链接：    http://poj.org/problem?id=2299
 4 题意：    求逆序对。
 5 算法：    树状数组+离散化。
 6 ***********************************************/
 7 #include<cstdio>
 8 #include<cstring>
 9 #include<algorithm>
10 #include<iostream>
11 using namespace std;
12 
13 const int mx=500005;
14 struct T
15 {
16     int x,di;
17 };
18 T s[mx];
19 int cut;
20 int c[mx];
21 long long p[mx];
22 
23 bool com1(T a,T b)
24 {
25     return a.x<b.x;
26 }
27 bool com2(T a,T b)
28 {
29     return a.di<b.di;
30 }
31 
32 int lowbit(int x)
33 {
34     return x&-x;
35 }
36 
37 void updata(int x)
38 {
39     if (x>cut) return ;
40     c[x]++;
41     updata(x+lowbit(x));
42 }
43 
44 int sum(int x)
45 {
46     if (x<=0) return 0;
47     return c[x]+sum(x-lowbit(x));
48 }
49 
50 int main()
51 {
52     int n;
53     while (scanf("%d",&n)&&n)
54     {
55         for (int i=0;i<n;i++)
56         {
57             scanf("%d",&s[i].x);
58             s[i].di=i;
59         }
60         sort(s,s+n,com1);
61         int temp=s[0].x;
62         s[0].x=cut=1;
63         for (int i=1;i<n;i++)
64         {
65             if (s[i].x==temp) s[i].x=cut;
66             else
67             {
68                 temp=s[i].x;
69                 s[i].x=++cut;
70             }
71         }
72         sort(s,s+n,com2);
73         memset(c,0,sizeof(c));
74         long long ans=0;
75         for (int i=0;i<n;i++)
76         {
77             ans+=i-sum(s[i].x);
78             updata(s[i].x);
79         }
80         printf("%lld
",ans);
81     }
82 }