16
1：逆序数：i<j,ai>aj,如：4 5 3 2 1,
4的逆序数个数0
5的逆序数个数0
3的逆序数4 5，个数2
2的你叙述4 5 3，个数3
1的逆序数4 5 3 2，个数4
2：离散化的方法
每加入一个数，该位置对应的sum标记1，并更新。
在该位置之后的到n的范围内的1的个数就是这个数的逆序数。
如加入4，逆序数0
加入5，逆序数0
加入3,位置4,5均有1，逆序数为2
加入2，，位置3,4,5均有1，逆序数为3
加入1，位置2 3 4 5，逆序数为4.
3最小逆序数对
先求出第一个序列的逆序数，然后用很巧妙的办法求下一个序列的逆序数，直到全部求出；
序列 4 5 2 1 3 6 ，此序列的逆序数为7，它等到的下一个序列为 5 2 1 3 6 4
看这个新序列的产生过程，首部删除4，尾部添加4
删除4，必然会使得这个序列的逆序数减少(4-1)个，因为4前面必定有4-1个数小于4
添加4，必然会使得这个序列的逆序数增加(6-4)个，因为4后面必定有6-4个数大于4
由此推出公式，假设移动的数为m，序列的逆序数=上一序列逆序数-(m-1)+(N-m)
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;#define maxn 10001#define inf 0x3f3f3f3fint ll[maxn<<2],rr[maxn<<2],sum[maxn<<2];int a[maxn];void build(int l,int r,int i){ll[i]=l;rr[i]=r;sum[i]=0;if(ll[i]==rr[i]){return ;}int m=(l+r)>>1,ls=i<<1,rs=ls|1;build(l,m,ls);build(m+1,r,rs);sum[i]=sum[ls]+sum[rs];}void update(int k,int i){if(ll[i]==rr[i]){sum[i]=1;return;}int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;if(k<=m){update(k,ls);}else{update(k,rs);}sum[i]=sum[ls]+sum[rs];}int finds(int l,int r,int i){if(ll[i]==l&&rr[i]==r){return sum[i];}int m=(ll[i]+rr[i])>>1,ls=i<<1,rs=ls|1;if(r<=m){return finds(l,r,ls);}else if(l>m){return finds(l,r,rs);}else{return finds(l,m,ls)+finds(m+1,r,rs);}}int main(){int n;int ss;//freopen("in.txt","r",stdin);while(scanf("%d",&n)!=EOF){build(0,n+1,1);ss=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);update(a[i],1);ss+=finds(a[i]+1,n+1,1);// printf("%d ",ss);}// printf("\n");int mas=ss;//printf("%d\n",ss);for(int i=1;i<=n;i++){ss=ss-a[i]+(n-1-a[i]);// printf("%d ",ss);if(ss<mas)mas=ss;}printf("%d\n",mas);}}
不义而富且贵，于我如浮云。
