逆序对的两种求法

逆序对

对于一个数论(a_{1},a_{2}......a_{n}),定义有一对序列({i,j}),当且仅当(i<j)且(a_{i}>a_{j})为逆序对

本质是:一组数论，只能相邻的数进行交换，求得试数列为单调的最小交换次数

归并排序

归并排序是基于分治思想进行的，把区间([l,r])拆分成([l,mid])和([mid+1,r])两部分，分治下去进行排序，每次合并的复杂度就是当前[l,r]的长度，进行(log_{2}n)次分治,总长度为n，则
归并排序的复杂度为
(O(nlog_{2}n))

归并排序写法

void MergeSort(int l,int r){
    if(l == r)return;
    int mid = (l + r) >> 1;
    MergeSort(l, mid);//左边
    MergeSort(mid+1,r);//右边
    int i = l,j = mid + 1, t = l;//i是左边的,j是右边的
    while(i <= mid && j <= r){
        if(a[i] <= a[j])b[t++] = a[i++];//左边小
        else b[t++] = a[j++];
    }
    while(i <= mid)b[t++] = a[i++];//右边部分多
    while(j <= r)b[t++] = a[j++];//左边部分多
    for(int k = l;k <= r; k++)a[k] = b[k];//及时更新
}

而对于求逆序对，由于合并所以左边和右边都是一组有序的数论。
左区间中剩下没加入的合并元素部分的一定就比右区间大
所以，在

else b[t++] = a[j++];

部分加一个ans += mid-i+1

则基于归并排序的求逆序对模板为

void MergeSort(int l,int r){
    if(l == r)return;
    int mid = (l + r) >> 1;
    MergeSort(l, mid);//左边
    MergeSort(mid+1,r);//右边
    int i = l,j = mid + 1, t = l;//i是左边的,j是右边的
    while(i <= mid && j <= r){
        if(a[i] <= a[j])b[t++] = a[i++];//左边小
        else b[t++] = a[j++],ans += mid - i + 1;
    }
    while(i <= mid)b[t++] = a[i++];//右边部分多
    while(j <= r)b[t++] = a[j++];//左边部分多
    for(int k = l;k <= r; k++)a[k] = b[k];//及时更新
}

模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];
int ans = 0;
void MergeSort(int l, int r){
    if(l == r)return;
    int mid = (l + r) >> 1;
    MergeSort(l, mid);//左边
    MergeSort(mid + 1, r);//右边
    int i = l, j = mid + 1, t = l;//i是左边的,j是右边的
    while(i <= mid && j <= r){
        if(a[i] <= a[j])b[t++] = a[i++];//左边小
        else b[t++] = a[j++], ans += mid - i + 1;
    }
    while(i <= mid) b[t++] = a[i++];//右边部分多
    while(j <= r) b[t++] = a[j++];//左边部分多
    for(int k = l; k <= r; k++) a[k] = b[k];//及时更新
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1 ; i <= n; i++){
        scanf("%d", &a[i]);
    }
    MergeSort(1, n);
    printf("%d
", ans);
    return 0;
}

树状数组

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 5e5 + 5;
int a[N], b[N], c[N];
int n;
bool cmp(int x,int y){
    if(a[x] == a[y]) return x < y;
    return a[x] < a[y];
}
int lowbit(int x){
    return x & (-x);
}
void add(int x,int y){//单点修改
    for(; x <= n; x += lowbit(x)) c[x]+=y;
}
int query(int x){//[1,x]和
    int ans = 0;
    for(; x > 0; x -= lowbit(x)) ans += c[x];
    return ans;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = i;
    sort (b + 1, b + n + 1, cmp);
    ll ans = 0;
    for (int i = 1; i <= n; ++i) add(b[i], 1), ans += i - query (b[i]);
    printf ("%lld
", ans);
    return 0;
}