题解：P1908 逆序对

yrteop_maerD · 2025-12-15 19:03:29 · 题解

有两种解法，归并排序和树状数组。

这里详细介绍归并排序做法。

假设对于区间 [L,R]，我们递归分治处理完了 [L,mid] 和 [mid+1,R] 的答案，那么此时我们该怎么做呢？

考虑正常归并排序流程，让两个指针分别从 L 和 mid+1 开始，哪边更小就把哪个丢入辅助数组中。

那么我们考虑，当出现了左边的 A_{l} 大于右边的 A_{r} 这种情况时，因为已经是分别排好序的，那么从当前的 A_l 一直到 A_{mid} 肯定都是比我现在这个 A_r 要更大的，这些都构成了逆序对，直接计入答案。

反之，不进行任何更新答案的操作，正常往后排序就行。

代码如下。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[1000005];
int b[1000005];
int ans;

inline void ms(int l,int r){
    if (l==r){
        return;
    }       
    int mid=(l+r)/2;
    ms(l,mid);
    ms(mid+1,r);

    int pl=l;
    int pr=mid+1;

    for (int i=l;i<=r;i++){
        if (pl>mid){
            b[i]=a[pr++];
        }
        else if (pr>r){
            b[i]=a[pl++];
        }
        else if (a[pl]<=a[pr]){
            b[i]=a[pl++];
        }
        else{
            b[i]=a[pr++];
            ans+=mid-pl+1;
        }
    }
    for (int i=l;i<=r;i++){
        a[i]=b[i];
    }
}

signed main(){
    cin>>n;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    ms(1,n);
    cout<<ans;
    return 0;
}