举个例子加以说明： 例子来源
假设给定的序列为 4 3 2 1，我们从左往右依次将给定的序列输入，每次输入一个数temp时，就将当前序列中大于temp的元素的个数计算出来，并累加到ans中，最后ans就是这个序列的逆序数个数。
| 序列的变化(下划线为新增加元素) |
序列中大于新增加的数字的个数 |
操作 |
| { } |
0 |
初始化时序列中一个数都没有 |
| {4 } |
0 |
往序列中增加4，统计此时序列中大于4的元素个数 |
| {4 3 } |
1 |
往序列中增加3，统计此时序列中大于3的元素个数 |
| {4 3 2} |
2 |
往序列中增加2，统计此时序列中大于2的元素个数 |
| {4 3 2 1} |
3 |
往序列中增加1，统计此时序列中大于1的元素个数 |
当所有的元素都插入到序列后，即可得到序列{4 3 2 1}的逆序数的个数为1+2+3=6.
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include <cstring>
#include <map>
using namespace std;
typedef long long LL;
int a[1000],b[1000],c[1000]={0};
int n;
int lowbit(int x)
{return x&(-x);
}
int Getsum(int i)
{int ans=0;while(i>0){ans+=c[i];i-=lowbit(i);}return ans;
}
void Update(int i,int v)
{while(i<=n){c[i]+=v;i+=lowbit(i);}return ;
}
void LS()
{int m=0;for(int i=1; i<=n; ++i)b[++m]=a[i];sort(b+1,b+1+m);m=unique(b+1,b+1+m)-b-1;for(int i=1; i<=n; ++i)a[i]=lower_bound(b+1,b+1+m,a[i])-b;return ;
}
int NXD()
{int ans=0;for(int i=1; i<=n; i++){Update(a[i],1);ans+=(i-Getsum(a[i]));//统计当前序列中大于a[i]的个数}return ans;
}
int main()
{int i,j,k;cin>>n;for(i=1; i<=n; i++){cin>>a[i];Update(i,a[i]);}//cout<<lowbit(n)<<endl;//cout<<Getsum(n-2)<<endl;//LS();// for(i=1; i<=n; i++)// cout<<a[i]<<" ";//cout<<endl;//cout<<NXD()<<endl;return 0;
}