[ An Ac a Day ^_^ ] hdu 3743 Frosh Week 离散化+树状数组

 1 #include<bits/stdc++.h>
 2 #define cl(a,b) memset(a,b,sizeof(a))
 3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int maxn=5e5+10;
 8 
 9 int tree[maxn],n;
10 
11 struct number
12 {
13     int id,num;
14 }num[maxn];
15 
16 bool cmp(number a,number b)
17 {
18     return a.num>b.num;
19 }
20 
21 int lowbit(int x)
22 {
23     return x&(-x);
24 }
25 
26 void add(int x)
27 {
28     int sum=0;
29     while(x<=n)
30     {
31         tree[x]++;
32         x+=lowbit(x);
33     }
34 }
35 
36 int getsum(int x)
37 {
38     int sum=0;
39     while(x>=1)
40     {
41         sum+=tree[x];
42         x-=lowbit(x);
43     }
44     return sum;
45 }
46 
47 int main()
48 {
49     while(~scanf("%d",&n)&&n)
50     {
51         for(int i=1;i<=n;i++)
52         {
53             scanf("%d",&num[i].num);
54             num[i].id=i;
55         }
56         sort(num+1,num+n+1,cmp);//排序
57         cl(tree,0);//初始化
58         ll sum=0;
59         add(num[1].id);
60         for(int i=2;i<=n;i++)//从大到小向树状数组中加入
61         {
62             sum+=getsum(num[i].id);//计算当前位数右边比它大的数的sum
63             add(num[i].id);//将当前数加入树状数组
64         }
65         printf("%lld\n",sum);
66     }
67     return 0;
68 }
69 /*
70 
71 3
72 3 1 2
73 
74 */