THE FIRST

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int n, m, a, b, c[N], h[N], tmp[N], ans;
void mergesort(int l, int r) {
    if(l >= r) return;
    int mid = (l + r) >> 1;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r) {
        if(c[i] <= c[j]) tmp[k++] = c[i++];
        else {
            tmp[k++] = c[j++];
            ans += mid - i + 1;
        }
    }
    while(i <= mid) tmp[k++] = c[i++];
    while(j <= r) tmp[k++] = c[j++];
    for(int i = l; i <= r; i++) c[i] = tmp[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i], c[i] = h[i];
    mergesort(1, n);
    cout << ans << "\n";
    cin >> m;
    for(int i = 1; i <= m; i++) {
        cin >> a >> b;
        if(a > b) {
            swap(a, b);
        }
        if(h[b] > h[a])
            ans++;
        else if(h[b] < h[a])
            ans--;
        for(int j = a + 1; j <= b - 1; j++) {
            if(h[j] > h[a])
                ans++;
            else if(h[j] < h[a])
                ans--;
            if(h[j] < h[b])
                ans++;
            else if(h[j] > h[b])
                ans--;
        }
        swap(h[a], h[b]);
        cout << ans << "\n";
    }
    return 0;
}

广告：
蒟蒻一只https://www.acgo.cn/discuss/rest/31665小电影链接