HDU 1394 Minimum Inversion Number（線段樹求最小逆序數對）

HDU 1394 Minimum Inversion Number（線段樹求最小逆序數對）

ACM

題目地址：HDU 1394 Minimum Inversion Number

題意：
給一個序列由[1,N]構成，可以通過旋轉把第一個移動到最後一個。
問旋轉後最小的逆序數對。

分析：
注意，序列是由[1,N]構成的，我們模擬下旋轉，總的逆序數對會有規律的變化。
求出初始的逆序數對再循環一遍就行了。

至於求逆序數對，我以前用歸並排序解過這道題：點這裡。
不過由於數據范圍是5000，所以完全可以用線段樹或樹狀數組來做：求某個數的作為逆序數對的後面部分的對數，可以在前面的數中查詢小於這個數的數的個數。
直接在線一邊加一邊查就行了，復雜度為O(nlogn)。

不過老實說，這題的單個數沒有太大，不然線段樹和樹狀數組都開不下的。所以求逆序數對的最佳算法應該是歸並排序解。

代碼：

/*
*  Author:      illuz 
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        1394_segment_tree.cpp
*  Create Date: 2014-08-05 10:08:42
*  Descripton:  segment tree 
*/

#include 
#include 
#include 
#include 
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)

#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)

typedef long long ll;

const int N = 5010;
const int ROOT = 1;

// below is sement point updated
struct seg {
    ll w;
};

struct segment_tree { 
    seg node[N << 2];

    void update(int pos) {
        node[pos].w = node[lson(pos)].w + node[rson(pos)].w;
    }

    void build(int l, int r, int pos) {
        if (l == r) {
            node[pos].w = 0;
            return;
        }
        int m = (l + r) >> 1;
        build(l, m, lson(pos));
        build(m + 1, r, rson(pos));
        update(pos);
    }

    // add the point x with y
    void modify(int l, int r, int pos, int x, ll y) {
        if (l == r) {
            node[pos].w += y;
            return;
        }
        int m = (l + r) >> 1;
        if (x <= m)
            modify(l, m, lson(pos), x, y);
        else
            modify(m + 1, r, rson(pos), x, y);
        update(pos);
    }

    // query the segment [x, y]
    ll query(int l, int r, int pos, int x, int y) {
        if (x <= l && r <= y)
            return node[pos].w;
        int m = (l + r) >> 1;
        ll res = 0;
        if (x <= m)
            res += query(l, m, lson(pos), x, y);
        if (y > m)
            res += query(m + 1, r, rson(pos), x, y);
        return res;
    }

    // remove the point that the sum of [0, it] is x, return its id
    int remove(int l, int r, int pos, ll x) {
        if (l == r) {
            node[pos].w = 0;
            return l;
        }
        int m = (l + r) >> 1;
        int res;
        if (x < node[lson(pos)].w)
            res = remove(l, m, lson(pos), x);
        else
            res = remove(m + 1, r, rson(pos), x - node[lson(pos)].w);
        update(pos);
        return res;
    }
} sgm;

int n, a[N], b[N], t, sum, mmin;

int main() {
    while (~scanf("%d", &n)) {
        sgm.build(1, n, ROOT);
        sum = 0;
        repf (i, 1, n)
            scanf("%d", &a[i]);
        for (int i = n; i >= 1; i--) {
            b[i] = sgm.query(1, n, ROOT, 1, a[i] + 1);
            sum += b[i];
            sgm.modify(1, n, ROOT, a[i] + 1, 1);
        }
        mmin = sum;
        repf (i, 1, n) {
            sum = sum - a[i] + (n - 1 - a[i]);
            mmin = min(mmin, sum);
        }
        cout << mmin << endl;
    }
    return 0;
}