rqnoj 173 Fish學數學 求逆序數，並歸排序的應用

題目是中文的。。 其實就是求一個序列的逆序對數，裸題。 用分治的思想來做，並歸排序稍微修改下就可以了。 代碼：

 /* 
 *   Author:        illuz <[email protected]> 
 *   Blog:          http://blog.csdn.net/hcbbt 
 *   File:          rqnoj173.cpp 
 *   Lauguage:      C/C++ 
 *   Create Date:   2013-08-30 09:45:28 
 *   Descripton:    rqnoj 1173, partitation  
 */  
#include <cstdio>  
#define rep(i, n) for (int i = 0; i < (n); i++)  
#define repu(i, a, b) for (int i = (a); i < (b); i++)  
  
const int MAXN = 1000100;  
int n, cnt, a[MAXN], t[MAXN];  
  
void merge(int l, int r) {  
    if (r - l <= 1) return;  
    int m = l + (r - l) / 2;  
    merge(l, m);  
    merge(m, r);  
    int p = l, q = m, i = l;  
    while (p < m || q < r)  
        if (q >= r || (p < m && a[p] <= a[q]))  
            t[i++] = a[p++];  
        else   
            t[i++] = a[q++], cnt += m - p;  
    repu(i, l, r) a[i] = t[i];  
}  
  
int main() {  
    scanf("%d", &n);  
    rep(i, n) scanf("%d", &a[i]);  
    cnt = 0;  
    merge(0, n);  
    printf("%d\n", cnt);  
    return 0;  
}