poj 2299 Ultra-QuickSort

//相同元素编号大较大 这么就可以避免处理有重复元素的情况。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=500000+5;
 6 struct item
 7 {
 8     int num;
 9     int id;
10     bool operator <(const item &a)const
11     {
12         if(num==a.num) return id>a.id;
13         return num>a.num;
14     }
15 }s[maxn];
16 int n;
17 int c[maxn];
18 int lowbit(int x)
19 {
20     return x&-x;
21 }
22 int sum(int x)
23 {
24     int ret=0;
25     while(x>0)
26     {
27         ret+=c[x];
28         x-=lowbit(x);
29     }
30     return ret;
31 }
32 void add(int x)
33 {
34     while(x<=n)
35     {
36         c[x]++;
37         x+=lowbit(x);
38     }
39 }
40 int main()
41 {
42     while(scanf("%d",&n)!=EOF&&n)
43     {
44         for(int i=1;i<=n;i++)
45         {
46             scanf("%d",&s[i].num);
47             s[i].id=i;
48         }
49         sort(s+1,s+1+n);
50         long long tot=0;
51         memset(c,0,sizeof(c));
52         for(int i=1;i<=n;i++)
53         {
54             tot+=sum(s[i].id-1);
55             add(s[i].id);
56         }
57         printf("%lld
",tot);
58     }
59     return 0;
60 }