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;
}