hdoj 1394 Minimum Inversion Number【樹狀數組求逆序數--逆序數的性質】

題目跳跳闆：​​1394​​

逆序數的求法：

逆序數對和即求每個數前面大于它的個數之和-----或者求每個數後面小于它的個數之和--

從數組的後面開始--每次先求已插入的小于它的數（即樹狀數組1-它的和）

再将它插入樹狀數組---

逆序數的性質：

兩個相鄰的數互換---逆序數+1或-1------通過這個性質我們應該會在已知逆序數的序列中将第一位移動最後一位後的逆序數了吧-.-

樹狀數組到0沒法結束---是以我們在樹狀數組中将數全部+1

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lowit(xx) (xx&-xx)
int SHU[5050];
int shu[5050];
int n,num,s;
void ADD(int xx)
{
  for (xx;xx<=n;xx+=lowit(xx))
  SHU[xx]++;
}
int QUERY(int xx)
{
  int lp=0;
  for (xx;xx>0;xx-=lowit(xx))
  {
    lp+=SHU[xx];
  }
  return lp;
}
int main()
{
  while(~scanf("%d",&n))
  {
    memset(SHU,0,sizeof(SHU));
    for (int i=1;i<=n;i++)
    scanf("%d",&shu[i]);
    num=0;
    for (int i=n;i>0;i--)
    {
      num+=QUERY(shu[i]+1);
    
      ADD(shu[i]+1);
    }
    s=num;
    for (int i=1;i<n;i++)
    { 
      num+=n-1-shu[i]*2;
      s=min(s,num); 
    }
    printf("%d\n",s);
  }
  return 0;
}