http://acm.hdu.edu.cn/showproblem.php?pid=1394
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5566 Accepted Submission(s): 3411
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)
const int N=5010;
struct Tree{
int l,r;
int cnt;
}tree[N<<2];
void PushUp(int rt){
tree[rt].cnt=tree[L(rt)].cnt+tree[R(rt)].cnt;
}
void build(int L,int R,int rt){
tree[rt].l=L;
tree[rt].r=R;
tree[rt].cnt=0;
if(tree[rt].l==tree[rt].r){
//scanf("%d",&tree[rt].x);
return ;
}
int mid=(L+R)>>1;
build(L,mid,L(rt));
build(mid+1,R,R(rt));
}
void update(int id,int rt){
if(tree[rt].l==tree[rt].r){
tree[rt].cnt++;
return ;
}
int mid=(tree[rt].l+tree[rt].r)>>1;
if(id<=mid)
update(id,L(rt));
else if(id>=mid+1)
update(id,R(rt));
PushUp(rt);
}
int query(int L,int R,int rt){
if(L==tree[rt].l && tree[rt].r==R)
return tree[rt].cnt;
int mid=(tree[rt].l+tree[rt].r)>>1;
int ans=0;
if(R<=mid)
ans+=query(L,R,L(rt));
else if(L>=mid+1)
ans+=query(L,R,R(rt));
else{
ans+=query(L,mid,L(rt));
ans+=query(mid+1,R,R(rt));
}
return ans;
}
int main(){
//freopen("input.txt","r",stdin);
int n,x[N];
while(~scanf("%d",&n)){
build(0,n-1,1);
int ans=0;
for(int i=0;i<n;i++){
scanf("%d",&x[i]);
ans+=query(x[i],n-1,1);
update(x[i],1);
}
int tmp=ans;
for(int i=0;i<n;i++){
tmp+=n-1-x[i]-x[i];
ans=min(ans,tmp);
}
printf("%d\n",ans);
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5010;
int n,arr[N],num[N];
int lowbit(int x){
return x&(-x);
}
void update(int id,int x){
while(id<=N){
arr[id]+=x;
id+=lowbit(id);
}
}
int Sum(int id){
int ans=0;
while(id>0){
ans+=arr[id];
id-=lowbit(id);
}
return ans;
}
int main(){
//freopen("input.txt","r",stdin);
while(~scanf("%d",&n)){
memset(arr,0,sizeof(arr));
int ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&num[i]);
ans+=Sum(n+1)-Sum(num[i]+1);
update(num[i]+1,1);
}
int tmp=ans;
for(int i=1;i<=n;i++){
tmp+=n-1-num[i]-num[i];
ans=min(ans,tmp);
}
printf("%d\n",ans);
}
return 0;
}
归并排序：
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=5005;
int num1[maxn],num2[maxn],temp[maxn];
int sum;
void Merge(int l,int mid,int r){
int p=0;
int i=l,j=mid+1;
while(i<=mid&&j<=r){
if(num1[i]>num1[j]){
sum+=mid-i+1;
temp[p++]=num1[j++];
}
else temp[p++]=num1[i++];
}
while(i<=mid)temp[p++]=num1[i++];
while(j<=r)temp[p++]=num1[j++];
for(i=0;i<p;i++)
num1[l+i]=temp[i];
}
void MergeSort(int l,int r){
if(l<r){
int mid=(l+r)>>1;
MergeSort(l,mid);
MergeSort(mid+1,r);
Merge(l,mid,r);
}
}
int main()
{
int n;
while(~scanf("%d",&n)){
for(int i=0;i<n;i++){
scanf("%d",&num1[i]);
num2[i]=num1[i];
}
sum=0;
MergeSort(0,n-1);
int ans=sum;
for(int i=0;i<n-1;i++){
sum+=n-num2[i]-num2[i]-1;
ans=ans<sum?ans:sum;
}
printf("%d\n",ans);
}
return 0;
}
HDU 1394 Minimum Inversion Number (归并排序 | 线段树 | 数状数组)
原文：http://www.cnblogs.com/jzy80/p/5032208.html