寒假Day30：逆序对树状数组/归并排序

这个是利用树状数组求得逆序对的AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include <iostream>
 5 #include<algorithm>
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 struct node
10 {
11     int x,id;
12 }a[500020];
13 
14 int b[500020],n;
15 ll c[500020];
16 
17 int cmp(node x,node y)
18 {
19     if(x.x!=y.x)
20         return x.x<y.x;
21     return x.id<y.id;
22 }
23 
24 int lowbit(int x)
25 {
26     return x&(-x);
27 }
28 
29 void add(int x,int k)
30 {
31     while(x<=n)
32     {
33         c[x]+=k;
34         x+=lowbit(x);
35     }
36 }
37 
38 ll sum(int x)
39 {
40     ll res=0;
41     while(x>=1)
42     {
43         res+=c[x];
44         x-=lowbit(x);
45     }
46     return res;
47 }
48 
49 int main()
50 {
51     while(~scanf("%d",&n)&&n)
52     {
53         memset(c,0, sizeof(a));
54         for(int i=1;i<=n;i++)
55         {
56             scanf("%d",&a[i].x);
57             a[i].id=i;//在原数组中的位置
58         }
59         sort(a+1,a+1+n,cmp);
60         for(int i=1;i<=n;i++)
61             b[a[i].id]=i;
62         ll w=0;
63         for(int i=1;i<=n;i++)
64         {
65             add(b[i],1);
66             w=w+i-sum(b[i]);
67         }
68         cout<<w<<endl;
69     }
70     return 0;
71 }

View Code

还可以用归并排序，但是我还没学归并排序的代码