HDU 1394 Minimum Inversion Number // 線段樹求逆序數

題目描述

HDU 1394 Minimum Inversion Number

解題思路

題目大意:

給出0~n-1的一個排列,每次可以把前m個數放在後面,eg:

a1 , a2 , …, an−1 , an (m=0)

a2 , a3 , …, an , a1 (m=1)

…

an , a1 , a2 , …, an−1 (m=n−1)

問在上述排列中, 逆序數最小為多少?

概念: ( ai , aj ) 是逆序對 當且僅當 i<j 時, ai > aj

求逆序數的思路:

1) 按定義: 暴力O( n2 )循環計算

2) 可以用線段樹來查詢區間[ ai+1 , n−1 ], 節點維護的資訊是在 ai 前面的，且比它大的數的個數. 複雜度優化到O( nlogn )

對于本題, 每移動一個元素,逆序數改變的公式為:

sum = sum + n - 2*a[i] - 1;

eg:

5 4 3 6 1 2 7 記目前排列的逆序數為 sum

則 移動一個元素之後得到序列

4 3 6 1 2 7 5

因為5移到最後,則逆序數減少了(5,4),(5,3),(5,2),(5,1) 共四個 即 ai−1 個

同時增加了 (6,5), (7,5) 共兩個 即 n−ai 個

是以 sum = sum - (a[i]-1) + (n-a[i]) = sum + n - 2*a[i] - 1;

參考代碼

#include <stdio.h>
#define lson rt<<1
#define rson rt<<1|1
#define mid ((l+r) >> 1)
const int MAX_N = ;
int sum[MAX_N << ];
int a[MAX_N];

void pushup(int rt){
    sum[rt] = sum[lson] + sum[rson];
}

void build(int l, int r, int rt){
    sum[rt] = ;
    if (l == r) return ;
    build(l, mid, lson);
    build(mid+, r, rson);
}

void update(int k, int l, int r, int rt){
    if (l == r){
        sum[rt] = ;
        return ;
    }
    if (k <= mid)   update(k, l, mid, lson);
    else    update(k, mid+, r, rson);
    pushup(rt);
}

int query(int L, int R, int l, int r, int rt){
    if (L <= l && r <= R){
        return sum[rt];
    }
    int ans = ;
    if (L <= mid)   ans += query(L, R, l, mid, lson);
    if (R > mid)    ans += query(L, R, mid+, r, rson);
    return ans;
}

int main(){
    int n;
    while (~scanf("%d", &n)){
        build(, n-, );
        int cnt = ;
        for (int i = ;i < n;++i){
            scanf("%d", a+i);
            cnt += query(a[i], n-, , n-, );
            update(a[i], , n-, );
        }
        int ans = cnt;
        for (int i = ;i < n;++i){
            cnt += n - *a[i] - ;
            if (cnt < ans)  ans = cnt;
        }
        printf("%d\n", ans);
    }
    return ;
}