逆序对问题求解
逆序对-如果存在l<r，并且X(l)<X(r)，则称为一个逆序对。逆序对的个数等于在朴素稳定排序情况下，相邻数交换的次数。
解法1：归并排序
如果我们将数组分成两块X(1)~X(i）、X(i+1)~X(n)，那么求左边某一个数y的逆序对，就是在求在左部，y的右边有多少数比他小以及在整个右部多少数比他小。
那么在归并的时候，这两块已经有序，所以只要用双指针，求出右部有多少数比他小即可。
不用求多变的理由：归并排序的本质是递归分治，最小的状态就是1个数的时候，左部的所有数的逆序关系会在排序的同时已经得知。
举个栗子：3 5 2 1 0 4 9
枚举法：枚举待测位置i，从i+1~n遍历，找出比他小的数的个数，枚举法可得的解有(3,2)，(3,1)，(3,0)，(5,2)，(5,1)，(5,0)，(5,4)，(2,1)，(2,0)，(1,0)。
归并排序法：
向下递归划分过程示意图
向上返回归并过程示意图
上述是归并排序排序结束向上层返回的示意图。
按照归并排序法，3因为只有一个数，无法累加逆序对，对5、2节点归并的时候，产生1个逆序对，1、0节点归并，产生1个逆序对，4、9不产生逆序对，3、25节点归并，产生1个逆序对，01、49节点归并时，产生0个逆序对，235、0149节点归并时，产生7个逆序对，其中间结果累加起来得到10个逆序对。
可行性分析：排序的过程是为了让我们不要重复计算逆序对，而借由归并排序和双指针，我们可以O(1)的复杂度得到当前情况下某个数的逆序对。
代码：
#include<cstdio>
using namespace std;
int A[10],n;
int megersort(int l,int r){
if(l>=r)return 0;
int mid=(l+r)/2;
int t=megersort(l,mid)+megersort(mid+1,r);
int L=l,R=mid+1,ans=l;
int *p=new int[n+1];//左部归并好的部分
for(int i=l;i<=mid;i++){
p[i]=A[i];
}
int *q=new int[n+1];//右部归并好的部分
for(int i=mid+1;i<=r;i++){
q[i]=A[i];
}
while(L<=mid&&R<=r){
if(p[L]<=q[R]){
A[ans++]=p[L++];
t+=R-mid-1;
}else{
A[ans++]=q[R++];
}
}
while(L<=mid){//左部有剩余
A[ans++]=p[L++];
t+=r-mid;
}
while(R<=r){
A[ans++]=q[R++];
}
return t;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&A[i]);
}
printf("逆序对:%d",megersort(1,n));
for(int i=1;i<=n;i++){
printf("%d ",A[i ]);
}
return 0;
}
解法2：树状数组
考虑一个序列，x1,x2……xn，假设我们已经知道这个序列有n个逆序对，那么我们只要考虑x(n+1)加进来会增加m个逆序对，n+m就是x1,x2……x(n+1)的总的逆序对个数。
用树状数组我们还需要一个东西-桶，为了避免遍历地去找前n个数有多少个比x(n+1)大，我们直接用桶做统计，并把它建成树状数组得到O(logn)的查询复杂度。
这里我们要提及桶的缺陷了，桶是有序的容器，但是桶和数据规模相关，假设数据的量少但是跨度大，桶是不适用的。
解决办法：我们需要的其实只是在这串数中所有数之间的大小关系，所以可以用一个Map，在不改变他们的大小关系的前提下，将他们统统映射为较小的数。
实现：将数据建立为一个大根堆或者是set【去除重复元素】，用hash或者是map，依次从大根堆【set:有序集合、逆向迭代】里取元素并作出映射。
#include<cstdio>
#include<set>
#include <map>
#define lowbit(x) x&(-x)
using namespace std;
int arr[105],tree[105],n;
int getsum(int locate){
int sum=0;
locate--;//当要求小于等于x的元素的个数的时候，为了不算上x，所以要从x-1开始算
while(locate){
sum+=tree[locate];
locate-=lowbit(locate);
}
return sum;
}
void update(int locate){
while(locate<=n){
tree[locate]++;
locate+=lowbit(locate);
}
}
int main(){
int cnt=1,total=0,query,re;
map<int,int>Map;
set<int>Set;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&arr[i]);
Set.insert(arr[i]);
}
for(set<int>::reverse_iterator it = Set.rbegin(); it != Set.rend(); it++){
Map.insert(pair<int,int>(*it,cnt));
printf("元素:%d 权重:%d\n",*it,cnt++);
}
for(int i=1;i<=n;i++){
query=Map[arr[i]];
total+=re=getsum(query);
update(query);
printf("比%d大的前面元素有%d个\n",arr[i],re);
}
printf("逆序对:%d",total);
return 0;
}
再谈优化：c++的map用的是平衡树，查找效率在O(logn)，优化可以考虑c++11的hash，查找O(1)的复杂度：
#include<cstdio>
#include<set>
#include<unordered_map>
#define lowbit(x) x&(-x)
using namespace std;
int arr[105], tree[105], n;
int getsum(int locate) {
int sum = 0;
locate--;
while (locate) {
sum += tree[locate];
locate -= lowbit(locate);
}
return sum;
}
void update(int locate) {
while (locate <= n) {
tree[locate]++;
locate += lowbit(locate);
}
}
int main() {
int cnt = 1, total = 0, query, re;
unordered_map<int, int>Map;
set<int>Set;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
Set.insert(arr[i]);
}
for (set<int>::reverse_iterator it = Set.rbegin(); it != Set.rend(); it++) {
Map.insert(pair<int, int>(*it, cnt));
printf("元素:%d 权重:%d\n", *it, cnt++);
}
for (int i = 1; i <= n; i++) {
query = Map[arr[i]];
total += re = getsum(query);
update(query);
printf("比%d大的前面元素有%d个\n", arr[i], re);
}
printf("逆序对:%d", total);
return 0;
}