【题意】：给出n个数组成的一个序列，我们可以把前m个数移到序列的后面，这样我们一共可以得到n个不同的序列。求这n个序列中，逆序对最小为多少。
【题解】：可以利用树状数组或者线段树在O(nlogn)时间里求出初始序列的逆序对，然后每次用O(1)的时间推出每移动一个数到序列后面之后的逆序对。
总复杂度O(nlogn + n)。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 using namespace std;
10 #define pb push_back
11 #define lc(x) (x << 1)
12 #define rc(x) (x << 1 | 1)
13 #define lowbit(x) (x & (-x))
14 #define ll long long
15 #define maxn 5005
16 const int inf = 1 << 30;
17 int sum[maxn], n, val[maxn];
18
19 void update(int x) {
20 for(int i = x; i < maxn; i += lowbit(i))
21 sum[i]++;
22 }
23
24 int SUM(int x) {
25 int res = 0;
26 for(int i = x; i; i -= lowbit(i))
27 res += sum[i];
28 return res;
29 }
30
31 int main() {
32 while(~scanf("%d", &n)) {
33 memset(sum, 0, sizeof(sum));
34 int ans = inf, tmp = 0;
35 for(int i = 0; i < n; i++) {
36 scanf("%d", &val[i]);
37 tmp += SUM(n) - SUM(val[i]);
38 update(val[i]+1);
39 }
40 for(int i = 0; i < n - 1; i++) {
41 tmp += n - 2 * val[i] - 1;
42 ans = min(ans, tmp);
43 }
44 cout << ans << endl;
45 }
46 return 0;
47 }
48