利用分治求一次逆序數，然后每次把第一個元素放到末尾，設該交換元素的值為x，設上一次求得的逆序數為y，那么此時的逆序數等于y - x + (n - x - 1)，減去x是因為x作為第一個元素，其后共有x個元素小于x，移動x會導致逆序數減少x個，而加上 (n - x - 1) 是因為將x移動到末尾，其前面(n - 1)個元素中會有(n - x - 1)個元素大于x。

    此題的復雜度在于求第一次逆序數O(nlgn)，后面每次移動元素求更新后的逆序數時間是O(1)，因此總的復雜度為(nlgn)。

AC代碼：

#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn = 5000 +5;int a[maxn], c[maxn];int solve(int l, int r){    int mid = (l + r) / 2;    if( l == r) return 0;    int ans = 0;    ans += solve(l, mid) + solve(mid + 1, r);    // Merge    int b[maxn];    int x = l, y= mid + 1;    int  k = 0;    while(x <= mid && y <= r){        if(a[x] <= a[y]){            b[k++] = a[x++];        }        else {            ans += mid + 1 - x;            b[k++] = a[y++];        }    }    while(x <= mid) b[k++] = a[x++];    while(y <= r) b[k++] = a[y++];    k = 0;    for(int i = l; i <= r; ++i) a[i] = b[k++];    return ans;}int main(){    int n;    while(scanf("%d", &n) == 1){        for(int i = 0; i < n; ++i){            scanf("%d", &a[i]);        }        memcpy(c, a, sizeof(a));        int ans = solve(0, n-1);        int x = ans;        for(int i = 0; i < n; ++i){            ans = min(ans, x + n - 1 - 2 * c[i]);            x = x + n - 1 - 2 * c[i];        }        PRintf("%d/n",ans);    }    return 0;}
線段樹也能做這個題，每個區間保存的值代表[l, r]中總出現多少元素，每次加入x元素時，查找區間[x + 2, n]即可得到該元素的加入會增加多少逆序數。
貼上線段樹代碼：
#include<cstdio>#define min(x,y) (x) < (y) ? x : yconst int maxn = 4 * 5000 + 5;int a[5000 + 5];struct node{    int L, R;    int cnt;}t[maxn];void Build(int l, int r, int cur){    t[cur].L = l, t[cur].R = r;    t[cur].cnt = 0;    if(l == r) return;    int mid = (l + r) / 2;    Build(l, mid, cur << 1);    Build(mid + 1, r, (cur << 1) + 1);}void add(int c, int cur){    int l = t[cur].L, r = t[cur].R;    t[cur].cnt++;    if(l == r) return;    int mid = (l + r) / 2;    if(c <= mid) add(c, cur << 1);    else add(c, (cur << 1) + 1);}int find1(int l, int r, int cur){ //search the Inversion (logn)    int l1 = t[cur].L, r1 = t[cur].R;    if(l == l1 && r == r1) return t[cur].cnt;    int mid = (l1 + r1) / 2;    if(r <= mid) return find1(l, r, cur << 1);    else if(l >= mid + 1) return find1(l, r, (cur << 1) + 1);    else return find1(l, mid, cur << 1) + find1(mid + 1, r, (cur << 1) + 1);}int main(){    int n;    while(scanf("%d", &n) == 1){        Build(1, n, 1);        int ans = 0;        for(int i = 0; i < n; ++i){            scanf("%d", &a[i]);            a[i]++;            add(a[i], 1);            if(a[i] + 1 <= n) ans += find1(a[i] + 1, n, 1);        }        int x = ans;        for(int i = 0; i < n; ++i){            ans = min(ans, x + n + 1 - 2 * a[i]);            x = x + n + 1 - 2 * a[i];        }        printf("%d/n",ans);    }    return 0;}如有不當之處歡迎指出！