树状数组求逆序对附HDU1394

清楚的图解，解释树状数组求逆序对的方法，转载：https://blog.csdn.net/ssimple_y/article/details/53744096

思路：因为数字[1,n]，把a[i]放到末尾，逆序对数量会增加n-a[i]个，即比它大的数字个数，

减少a[i]-1个，即比它小的数字个数

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <map>
 4 #include <queue>
 5 #include <string>
 6 #include <stack>
 7 #include <vector>
 8 #include <list>
 9 #include <cstdio>
10 #include <cstring>
11 #include <cmath>
12 using namespace std;
13 #define ll long long
14 #define pb push_back
15 #define fi first
16 #define se second
17 
18 const int N = 5e3+10;
19 int a[N],c[N];
20 int n;
21 
22 inline int lb(int x){
23     return x&(-x);
24 }
25 
26 void update(int inx){
27     for(int i = inx; i <= n; i += lb(i)){
28         ++c[i];
29     }
30 }
31 
32 int sum(int inx){
33     int res = 0;
34     for(int i = inx; i >= 1; i -= lb(i)){
35         res += c[i]; 
36     }
37 
38     return res;
39 }
40 
41 void solve(){
42 
43     while(~scanf("%d",&n)){
44         memset(c,0,sizeof(c));
45         int tot = 0;
46         for(int i = 1; i <= n; ++i){
47             scanf("%d",a+i);
48             update(++a[i]);  //这里处理一下0，使得更新和查询不会死循环
49             tot += i - sum(a[i]);
50         }
51         int Min = tot;
52         for(int i = 1; i <= n; ++i){
53             tot += n - 2*a[i] + 1;
54             Min = min(tot,Min);
55         }
56         printf("%d
",Min);
57     }
58 
59 }
60 
61 int main(){
62  
63   //  ios::sync_with_stdio(false);
64   //  cin.tie(0); cout.tie(0);
65     solve();
66 
67     return 0;
68 }

树状数组求逆序对 附HDU1394

树状数组求逆序对附HDU1394