HDU 1394Minimum Inversion Number（线段树）

题目大意是说给你一个数组(N个)，没戏可以将其首部的k(k<N)个元素移动至尾部，这样总共会形成N个序列

现在要求这n个序列中逆序对数最少的那一个序列有多少个逆序对

最初的确是没太多思路，就算知道线段书可以球某一个序列的逆序对数，但是这里要求n次，就没有太多把握了

而最后的方法其实的确是只用求一次的，由于给出的n个数字是0～n-1的一个排列，所以考虑吧a[0]放到最后一个位置时，那以它作为起点的逆序对数相应的会减少a[0]个(这是因为塔处在地一个位置，所有比它晓得数都会在其后方)， 然后考虑a[0]已经被移动到最后一个位置，那么相应的这个序列的逆序对数会增加n-a[0]个

所以只要在一遍线段书或树状数组求出开始时的逆序对数后，后面的可以由它递推得到

#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1e9
#define inf (-((LL)1<<40))
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FOPENIN(IN) freopen(IN, "r", stdin)
#define FOPENOUT(OUT) freopen(OUT, "w", stdout)
template<class T> T CMP_MIN(T a, T b) { return a < b; }
template<class T> T CMP_MAX(T a, T b) { return a > b; }
template<class T> T MAX(T a, T b) { return a > b ? a : b; }
template<class T> T MIN(T a, T b) { return a < b ? a : b; }
template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

typedef __int64 LL;
//typedef long long LL;
const int MAXN = 5005;
const int MAXM = 100005;
const double eps = 1e-10;
const LL MOD = 1000000007;

int c[MAXN], a[MAXN], id[MAXN], N;

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

void update(int k, int x)
{
    while(k <= N)
    {
        c[k] += x;
        k += lowbit(k);
    }
}

int getSum(int k)
{
    int sum = 0;
    while(k > 0)
    {
        sum += c[k];
        k -= lowbit(k);
    }
    return sum;
}

int cmp(int i, int j)
{
    return a[i] > a[j];
}

int getCnt()
{
    for(int i=1;i<=N;i++) id[i] = i;
    sort(id+1, id + N + 1, cmp);
    mem0(c);
    int cnt = 0;
    for(int i=1;i<=N;i++)
    {
        cnt += getSum(id[i]);
        update(id[i], 1);
    }
    return cnt;
}

int main()
{
    while(scanf("%d", &N) == 1)
    {
        for(int i=1;i<=N;i++) scanf("%d", &a[i]);
        int ans = getCnt(), x = ans;
        for(int i=1;i<N;i++)
        {
            x = x + N - 2 * a[i] - 1;
            ans = MIN(ans, x);
        }
        printf("%d
", ans);
    }
    return 0;
}