题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394
题意：给你一个0 — n-1的排列，对于这个排列你可以将第一个元素放到最后一个，问你可能得到的最多逆序对的个数
求出原始序列的逆序对的数目，然后进行n－1次将第一个元素放到最后一个的操作，每次操作后可以用O(1)复杂度求得新序列的逆序对数目
此题的关键点在于求出原始序列逆序对的数目，可以使用树状数组， 线段树， 归并等方法。
下面是树状数组的解法
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 5010
using namespace std; int c[maxn], arr[maxn], n; int lowbit(int x); void add(int x, int u); int sum(int x); int main(void)
{
while (scanf("%d", &n) != EOF)
{
int ans = ;
memset( c, , sizeof(c));
for (int i = ; i < n; ++i)
{
scanf("%d", arr + i);
arr[i] += ;
ans += i - sum( arr[i]);
add( arr[i], );
}
int pre = ans, tmp;
for (int i = ; i < n - ; ++i)
{
tmp = pre - (arr[i] - ) + (n - arr[i]);
ans = min( ans, tmp);
pre = tmp;
}
printf("%d\n", ans);
}
return ;
} int lowbit(int x)
{
return x&(-x);
} int sum(int x)
{
int result = ;
while (x > )
{
result += c[x];
x -= lowbit(x);
}
return result;
} void add(int x, int u)
{
while (x <= n)
{
c[x] += u;
x += lowbit(x);
}
}