树状数组简单题(第一道树状数组哈)
唯一有点意思的是这道题目需要离散化。详见代码
题意: 求一组数的逆序数
1 //离散化+树状数组
2 #include<cstring>
3 #include<algorithm>
4 #include<cstdio>
5 using namespace std;
6 const int MAX=500000+10;
7 struct node
8 {
9 int val,pos;
10 }v[MAX];
11 int num[MAX],n,c[MAX];
12 int cmp(node a,node b)
13 {
14 return a.val<b.val;
15 }
16 int lowbit(int x)
17 {
18 return x&(-x);
19 }
20 void add(int x)
21 {
22 while(x<=n)
23 {
24 c[x]++;
25 x+=lowbit(x);
26 }
27 }
28 int sum(int x)
29 {
30 int ans=0;
31 while(x>0)
32 {
33 ans+=c[x];
34 x-=lowbit(x);
35 }
36 return ans;
37 }
38 int main()
39 {
40 long long summ;
41 while(scanf("%d",&n)&&n)
42 {
43 memset(c,0,sizeof(c));
44 for(int i=1;i<=n;i++)
45 {
46 scanf("%d",&v[i].val);
47 v[i].pos=i;
48 }
49 sort(v+1,v+n+1,cmp);
50 for(int i=1;i<=n;i++)
51 {
52 num[v[i].pos]=i; //离散化部分
53 }
54 int ans=0;
55 summ=0;
56 for(int i=1;i<=n;i++)
57 {
58 add(num[i]);
59 ans=sum(num[i]-1);
60 summ+=(i-1-ans);
61 }
62 printf("%lld\n",summ);
63 }
64 return 0;
2 #include<cstring>
3 #include<algorithm>
4 #include<cstdio>
5 using namespace std;
6 const int MAX=500000+10;
7 struct node
8 {
9 int val,pos;
10 }v[MAX];
11 int num[MAX],n,c[MAX];
12 int cmp(node a,node b)
13 {
14 return a.val<b.val;
15 }
16 int lowbit(int x)
17 {
18 return x&(-x);
19 }
20 void add(int x)
21 {
22 while(x<=n)
23 {
24 c[x]++;
25 x+=lowbit(x);
26 }
27 }
28 int sum(int x)
29 {
30 int ans=0;
31 while(x>0)
32 {
33 ans+=c[x];
34 x-=lowbit(x);
35 }
36 return ans;
37 }
38 int main()
39 {
40 long long summ;
41 while(scanf("%d",&n)&&n)
42 {
43 memset(c,0,sizeof(c));
44 for(int i=1;i<=n;i++)
45 {
46 scanf("%d",&v[i].val);
47 v[i].pos=i;
48 }
49 sort(v+1,v+n+1,cmp);
50 for(int i=1;i<=n;i++)
51 {
52 num[v[i].pos]=i; //离散化部分
53 }
54 int ans=0;
55 summ=0;
56 for(int i=1;i<=n;i++)
57 {
58 add(num[i]);
59 ans=sum(num[i]-1);
60 summ+=(i-1-ans);
61 }
62 printf("%lld\n",summ);
63 }
64 return 0;
65 }