题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394
题意：求某种规定序列中的最小逆序数。
递推比较最小那部分比较简单，就不说了。
主要想说：求逆序数可以用构建线段树的方法来做。其实思想和计数排序的思想差不多。每次处理a[i]时，先统计一下已经被计数的前几个数的计数和。（比较的是值。）然后再更新这个计数和。这道题的数据范围和下标范围是一样的，所以可以直接做。
详见代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;#define Maxn 5005
#define lx x<<1
#define rx ((x<<1) + 1)
#define MID ((l + r)>>1)
int A[Maxn];
int S[Maxn<<2];void pushUp(int x)
{S[x] = S[lx] + S[rx];
}
void build(int l,int r,int x)
{if(l == r){S[x] = 0;return;}build(l,MID,lx);build(MID+1,r,rx);pushUp(x);
}
int query(int L,int R,int l,int r,int x)
{int ans = 0;if(L<=l && r<=R) return S[x];if(L<=MID) ans += query(L,R,l,MID,lx);if(R>=MID+1) ans += query(L,R,MID+1,r,rx);return ans;
}
void update(int p,int d,int l,int r,int x)
{if(l == r){S[x] +=d;return;}if(p<=MID) update(p,d,l,MID,lx);else update(p,d,MID+1,r,rx);pushUp(x);
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
#endifint n;int sum,ans,temp;while(scanf(" %d",&n)!=EOF){sum = ans = 0;build(0,n-1,1);for(int i=0;i<n;i++){scanf(" %d",&A[i]);temp = query(A[i],n-1,0,n-1,1);sum += temp;update(A[i],1,0,n-1,1);}ans = sum;//递推求解，每次A[i]都在首位，则分为大于它的部分和小于它的部分。for(int i=0;i<n;i++){sum += n-1-A[i] - A[i];ans = min(ans,sum);}printf("%d\n",ans);}return 0;
}
但是如果数据范围和下标范围不是一个范围的话，我们就不能直接用这个方法 做了。。试想，如果一个数有最大可以有十亿，难道我们要开一个十亿大小的数组来标记么。。这显然不现实。所以我们要对数据进行离散话，毕竟数据的数量达不到那么大。比如说这道题：http://poj.org/problem?id=2299。也是求逆序数。数据的范围特别大。但是数量比较少。非常适合离散化。
关于什么是离散话，参考：http://www.matrix67.com/blog/archives/108 和 http://baike.baidu.com/view/3392254.htm
那么离散化+线段树我们就可以做这道题了（不要忘了用long long，int存储不下最终结果）：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;#define Maxn 500005
#define lx x<<1
#define rx ((x<<1) + 1)
#define MID ((l + r)>>1)
#define LL long long
int rank[Maxn];
LL S[Maxn<<2];struct Node
{int val;int id;bool operator <(const Node &a) const{return val < a.val;}
} A[Maxn];void pushUp(int x)
{S[x] = S[lx] + S[rx];
}
void build(int l,int r,int x)
{if(l == r){S[x] = 0;return;}build(l,MID,lx);build(MID+1,r,rx);pushUp(x);
}
LL query(int L,int R,int l,int r,int x)
{LL ans = 0;if(L<=l && r<=R) return S[x];if(L<=MID) ans += query(L,R,l,MID,lx);if(R>=MID+1) ans += query(L,R,MID+1,r,rx);return ans;
}
void update(int p,int d,int l,int r,int x)
{if(l == r){S[x] +=d;return;}if(p<=MID) update(p,d,l,MID,lx);else update(p,d,MID+1,r,rx);pushUp(x);
}int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
#endifint n;LL ans = 0;int temp;while(scanf(" %d",&n)!=EOF){ans = 0;if(n == 0) break;build(0,n-1,1);for(int i=0;i<n;i++){scanf(" %d",&A[i].val);A[i].id = i;}sort(A,A+n);for(int i=0;i<n;i++) rank[A[i].id] = i;for(int i=0;i<n;i++){temp = rank[i];ans += query(temp+1,n-1,0,n-1,1);update(temp,1,0,n-1,1);}printf("%lld\n",ans);}return 0;
}
另外，求逆序数也可以用树状数组和归并排序来做。
用线段树属于平衡树做法的一种。