逆序对

佚名 6年前 (2019-04-14) 随笔 973人围观抢沙发百度已收录

逆序对

逆序对非常常见，有两种求解的方法，效率差不多，但是树状数组法较快。

归并排序

归并排序的思想就是递归分治，把要解决的区间分成两个区间比较\(a_i\)和\(a_j\)的大小（其中\(a_i\)属于左区间，\(a_j\)属于右区间，其实就是将左右区间合并、并排序），若\(a_i<a_j\),则将\(a_i\)复制到\(r_k\)中，然后将\(i\)和\(k\)都加\(11\)，否则将\(a_j\)复制到\(r_k\)中，将\(j,k\)加\(11\)，最后再将\(r_k\)移动到\(a_i\)中，然后继续合并；

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

void msort(int l, int r)
{
    if(l == r)
    return;
    int mid = (l + r) / 2;
    msort(l, mid);
    msort(mid + 1, r);
    int i = l;
    int j = mid + 1;
    int k = l;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j])
        {
            fu[k] = a[i];
            k++; i++;
        }
        else
        {
            fu[k] = a[j];
            k++;
            j++;
            ans += mid - i + 1;
        }
    }
    while (i <= mid)
    {
        fu[k] = a[i];
        k++;
        i++;
    }
    while (j <= r)
    {
        fu[k] = a[j];
        k++;
        j++;
    }
    for (int i = l; i <= r; i++)
    a[i] = fu[i];
}

树状数组

树状数组其实就是桶的思想进行一波优化所得出来的。每拿到一个值放入桶中，统计所有大于这个数的数量，然后累加，发现这正好可以用树状数组优化。当然在使用之前还是应该离散化一下，不然桶会炸的。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define lowbit(n) (n & (-n))
#define int long long
using namespace std;
int n, sum;
int a[1001000], b[1010000], tree[1000100];
void add(int x) {
    while (x <= n) {
        tree[x]++;
        x += lowbit(x);
    }
}
int query(int x) {
    int ans = 0;
    while (x > 0) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
bool cmp(const int &x, const int &y)
{
    if(b[x]==b[y]) return x > y;
    return b[x] > b[y];
}
signed main() 
{
    scanf("%lld", &n);
    for(register int i = 1; i <= n; i++) 
    {
        scanf("%lld", &b[i]);  
        a[i] = i;  
    }
    sort(a + 1, a + n + 1, cmp);  
    for (int i = 1; i <= n; i++)
    {
        add(a[i]);
        sum += query(a[i] - 1); 
    }
    printf("%lld", sum);
}