C. Insertion Sort

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int f1[N][N], f2[N][N], a[N], b[N], n;
map<int, int> save;
int ans;
int cal(int i, int j) {
    return f1[a[i]][j - 1] + f2[a[i]][j + 1];
}
void merge_sort(int l, int r) {
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid); merge_sort(mid + 1, r);
    int p = l, q = mid + 1, cur = l;
    while(p <= mid && q <= r) {
        if(a[p] <= a[q]) b[cur ++] = a[p ++], ans += q - mid - 1;
        else b[cur ++] = a[q ++];
    }
    while(p <= mid) b[cur ++] = a[p ++], ans += q - mid - 1;
    while(q <= r) b[cur ++] = a[q ++];
    for(int i = l; i <= r; i ++)
        a[i] = b[i];
    return;
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    vector<int> have(n + 1, 0);
    for(int i = 1; i <= n; i ++) have[i] = a[i];
    merge_sort(1, n);
    for(int i = 1; i <= n; i ++) a[i] = have[i];
    for(int i = 0; i < n; i ++) {
        for(int j = 1; j <= n; j ++) {
            f1[i][j] = f1[i][j - 1] + (a[j] > i);
        }
    }
    for(int i = 0; i < n; i ++) {
        for(int j = n; j >= 1; j --) {
            f2[i][j] = f2[i][j + 1] + (a[j] < i);
        }
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = i + 1; j <= n; j ++) {
            //swap(i, j)
            int ret = ans - cal(i, i) - cal(j, j) + cal(j, i) + cal(i, j) + 1;
            save[ret] ++;
        }
    }
    auto it = *save.begin();
    cout << it.first << ' ' << it.second << endl;
}

$f1\left[i\right]\left[j\right]:下标\le j中>if1[i][j]:\; 下标\; \backslash le\; j\; 中\; >\; i$f1[i][j]:下标≤j中>i的元素个数 f2[i][j]:下标≥j中<i的元素个数 枚举每一对$(i,j)(i,\; j)$(i,j)，先去掉其逆序对，然后根据两个状态更新 注意ret ++，这是因为$i\ne ji\; \backslash ne\; j$i​=j，那么两种情况必然都会被这个状态表示漏掉