P1908 逆序对

dzy15373891653 · 2025-06-06 19:02:17 · 题解

//本题用归并排序来写，大概是用O(n log n)的时间复杂度 
#include <iostream>

using namespace std;

const int N = 5e5 + 5;

long long n,a[N],b[N],ans;//a[i]存要排序的数组，b[i]作为中转，把已经排好序了的值再赋给a[i]，ans存答案 
//记得开 long long ans会爆int 
void merge (int l,int r) {//归并排序板子 

    if ((r - l) == 0) return ;//如果说这个区间的长度为1了就不需要继续往下分了，返回上一层 

    int mid = (l + r) / 2;//二分，以mid作为边界值 
    int i = l,j = mid + 1,cnt = l;//i为了不影响l值的变化而新开的一个变量，j取第二个区间的边界值，cnt存排序的长度 

    merge (l,mid);//让第一个区间进行二分，使得它变有序 
    merge (mid + 1,r);//同第一个一样 

    while (i <= mid && j <= r) {//遍历完这两个区间共同有的长度 

        if (a[i] <= a[j]) {//如果说第一个区间的最小值小于第二个区间的最小值，就把它加进b数组 
            b[cnt ++] = a[i];//加入数组 
            i ++;//跳到第一个序列的第二个元素 
        } else {//所以答案就加第一个区间的长度 
            ans += mid - i + 1;//因为如果他比第一个区间的最小值要小的话，那么说明第一个区间的所有数都比他大，又因为第一个区间的数都在他前面，所以都构成逆序对 
            b[cnt ++] = a[j];//同上 
            j ++;//更新元素 
        }
    }

    for (i ;i <= mid;i ++) b[cnt ++] = a[i];//如果说第一个区间还剩余元素没加，直接全加进去 
    for (j ;j <= r; j ++) b[cnt ++] = a[j];//同上 
    for (int k = l;k <= r;k ++) a[k] = b[k];//最后再赋给a数组已经排好序了的值 

}

int main () {

    cin >> n;

    for (int i = 1;i <= n;i ++) cin >> a[i];

    merge (1,n);//归并排序 

//  for (int i = 1;i <= n;i ++) {
//      cout << b[i] << '\n';
//  }

    cout << ans << '\n';//输出答案 
    return 0;//华丽结束 
}