暴力

const int N = 5e5 + 10;
int a[N];
int main (){
    int m = 0;
    while(cin >> m , m != 0){
        for (int i = 0;i < m;i++){
            scanf ("%d" , &a[i]);
        }
        int res = 0;
        for (int k = m;k >= 0;k--){
            for (int i = 0 ,j = 1; j < k;i++ , j++){
                if (a[i] > a[j]){
                    swap(a[i] , a[j]);
                    res ++;
                }
            }
        }//for
        printf ("%d\n" , res);
    }
    return 0;
}

归并排序求逆序对
如果对于2个数来说，a[i] > a[i + 1] 那么这2个数就是逆序对
根据题目要求这样子相邻的2个数是需要交换的
交换后这2个数就不是逆序对了
对于最后要求的序列是一个单调上升的序列，则逆序对是数量是0
所以要求要交换的操作次数，其实就是求逆序对的个数
利用归并排序求逆序对
比如 9 2 1
有3个逆序对 92 91 21
先交换9和2（不能交换91 因为要交换相邻的2个数）
交换后变成了2 9 1 91还是逆序对，现在可以交换了
变成2 1 9 还剩一个逆序对21
交换后变成了 1 2 9 所以一共需要交换3次
时间复杂度O(nlogn)

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5 + 10;
typedef long long LL;
int a[N];
int temp[N];
LL merge_sort(int l ,int r){
    if (l >= r) return 0;
    int mid = l + r >> 1;
    int i = l;
    int j = mid + 1;
    //mid左边的逆序对+mid右边的逆序对
    LL res = merge_sort(l , mid) + merge_sort(mid + 1 , r);
    //处理一个元素在左一个元素在右的情况
    //现在左边是一个单调上升的序列，右边也是一个单调上升的序列
    int k = 0;
    while(i <= mid && j <= r){
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else{ //i后面的元素都是大于a[j]
            temp[k++] = a[j++];
            res += mid - i + 1;
        }
    }
    while(i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (i = l , j = 0; i <= r;i++ , j++)
        a[i] = temp[j];
    return res;
}
int main (){
    int m = 0;
    while(cin >> m , m != 0){
        for (int i = 0;i < m;i++){
            scanf("%d" , &a[i]);
        }
        cout << merge_sort(0 , m - 1) << endl;
    }
    return 0;
}