摘要：
算法>；11#包括<；（-x）；i+=磅（i））｛28++c[i]；29｝30｝3132英寸（intinx）｛33英寸=0；34英寸（inti=inx；&；sizeof（c））；i<；=n；50｝51英寸最小值=tot；i＜=n最小值）；68};
清楚的图解，解释树状数组求逆序对的方法，转载：https://blog.csdn.net/ssimple_y/article/details/53744096
题目：https://vjudge.net/problem/HDU-1394
思路：因为数字[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 }