题目链接：http://poj.org/problem?id=2299
求逆序数的经典题，求逆序数可用树状数组，归并排序，线段树求解，本文给出树状数组，归并排序，线段树的解法。
归并排序：
#include<cstdio>
#include<iostream>
using namespace std;
#define max 500002
int arr[max],b[max];//b[]为临时序列，arr[]为待排序数列，结果在arr[]中
int tp[max];
long long cnt=;//总逆序数
void Merge(int a[],int start,int mid,int end){
int i =start,j=mid+,k=start;
while(i<=mid&&j<=end){
if(a[i]<=a[j]){
cnt+=j-mid-;
b[k++]=a[i++];
}else{
cnt+=j-k;
b[k++]=a[j++];
}
}
while(i<=mid){
cnt+=end-mid;
b[k++]=a[i++];
}
while(j<=end){
b[k++]=a[j++];
}
for(int i=start;i<=end;i++){
a[i]=b[i];
}
}
void MergeSort(int a[], int start,int end){
if(start<end){
int mid=(start+end)/;
MergeSort(a,start,mid);
MergeSort(a,mid+,end);
Merge(a,start,mid,end);
}
}
int main(){
int n;
while(~scanf("%d",&n)&&n){
for(int i=;i<n;i++){
scanf("%d",&arr[i]);
}
cnt=;
MergeSort(arr,,n-);
printf("%I64d\n",cnt/);
}
return ;
}
树状数组：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&(-x))
using namespace std;
const int MAX = ;
struct data{
int id,val;
}num[MAX];
int n, C[MAX];
bool cmp(data a, data b){
return a.val>b.val;
}
void add(int i){
while(i<=n){
C[i]+=;
i+=lowbit(i);
}
}
long long sum(int i){
long long ans = ;
while(i>){
ans+=C[i];
i-=lowbit(i);
}
return ans;
} int main(){
while(scanf("%d",&n)&&n){
memset(C,,sizeof(C));
for(int i=;i<n;i++){
num[i].id=i+;
scanf("%d",&num[i].val);
}
sort(num,num+n,cmp);//离散化，将数组按降序排序，再求下标的逆序数，下标的逆序数与值逆序数相等
long long ans = ;
for(int i=;i<n;i++){
ans+=sum(num[i].id-);//求在i前面比第i个数大的数的个数
add(num[i].id);
}
printf("%I64d\n", ans);
}
return ;
}
线段树( 以HDU1394 Minimum Inversion Number为例)：
#include<iostream>
#include<cstdio>
#include<cstdlib>#include<algorithm>
const int INF = 0x3F3F3F3F;
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define N 5008
int sum[N<<], a[N];
inline void pushUp(int rt){
sum[rt] = sum[rt << ] + sum[rt << | ];
} int query(int a, int b, int l, int r, int rt){
if(a <= l && b >= r){
return sum[rt];
}
int m=(l + r) >> ;
int ret=;
if(a <= m){
ret += query(a, b, lson);
}
if(b > m){
ret += query(a, b, rson);
}
return ret;
}
void update(int x, int val, int l, int r, int rt){
if(l == r){
sum[rt] = val;
}else{
int m = (l + r)/;
if(x <= m){
update(x, val, lson);
}else{
update(x, val, rson);
}
pushUp(rt);
}
} int main(){
int n;
while(~scanf("%d", &n)){
memset(sum, , sizeof(sum));
int ans = ;
for(int i = ; i < n; i++){
scanf("%d", &a[i]);
a[i]++;
ans += query(a[i] + , n, , n , );
update(a[i], , , n, );
}
int tp = ans;
for(int i = ; i < n - ; i++){
tp += n - * a[i] + ;
ans = min(ans , tp);
}
printf("%d\n",ans);
}
}