【題意】：給出n個數(shù)組成的一個序列，我們可以把前m個數(shù)移到序列的后面，這樣我們一共可以得到n個不同的序列。求這n個序列中，逆序?qū)ψ钚槎嗌佟?br />
【題解】：可以利用樹狀數(shù)組或者線段樹在O(nlogn)時間里求出初始序列的逆序?qū)Γ缓竺看斡肙(1)的時間推出每移動一個數(shù)到序列后面之后的逆序?qū)Α?br /> 總復(fù)雜度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