hdu 1394(BIT求逆序数)

题意：有长度为n的序列，序列的数字是0～n-1组成，然后这个序列可以看做环，那么就有n个长度为n的序列，问n个序列里最小逆序数是多少。
题解：先把初始序列的逆序数算出来，然后移动每一个开头数字a到后面，逆序数变化的是比a大的数字逆序数加一，比a小的逆序数减一，所以按这个规律再循环一次找最小值就可以了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5005;
int n, C[N], a[N];

int lowbit(int x) {
    return x & (-x);
}

int Sum(int x) {
    int ret = 0;
    while (x > 0) {
        ret += C[x];
        x -= lowbit(x);
    }
    return ret;
}

void Add(int x, int d) {
    while (x <= n) {
        C[x] += d;
        x += lowbit(x);
    }
}

int main() {
    while (scanf("%d", &n) == 1) {
        memset(C, 0, sizeof(C));
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            Add(a[i] + 1, 1);
            sum += i - Sum(a[i] + 1);
        }
        int res = sum;
        for (int i = 1; i < n; i++) {
            sum = sum + ((n - 1 - a[i]) - a[i]);
            res = min(res, sum);
        }
        printf("%d\n", res);
    }
    return 0;
}