HDU 1394Minimum Inversion Number（线段树）

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 1e9
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FOPENIN(IN) freopen(IN, "r", stdin)
23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)
24 template<class T> T CMP_MIN(T a, T b) { return a < b; }
25 template<class T> T CMP_MAX(T a, T b) { return a > b; }
26 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
27 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
28 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
29 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
30 
31 typedef __int64 LL;
32 //typedef long long LL;
33 const int MAXN = 5005;
34 const int MAXM = 100005;
35 const double eps = 1e-10;
36 const LL MOD = 1000000007;
37 
38 int c[MAXN], a[MAXN], id[MAXN], N;
39 
40 int lowbit(int x)
41 {
42     return x & (-x);
43 }
44 
45 void update(int k, int x)
46 {
47     while(k <= N)
48     {
49         c[k] += x;
50         k += lowbit(k);
51     }
52 }
53 
54 int getSum(int k)
55 {
56     int sum = 0;
57     while(k > 0)
58     {
59         sum += c[k];
60         k -= lowbit(k);
61     }
62     return sum;
63 }
64 
65 int cmp(int i, int j)
66 {
67     return a[i] > a[j];
68 }
69 
70 int getCnt()
71 {
72     for(int i=1;i<=N;i++) id[i] = i;
73     sort(id+1, id + N + 1, cmp);
74     mem0(c);
75     int cnt = 0;
76     for(int i=1;i<=N;i++)
77     {
78         cnt += getSum(id[i]);
79         update(id[i], 1);
80     }
81     return cnt;
82 }
83 
84 int main()
85 {
86     while(scanf("%d", &N) == 1)
87     {
88         for(int i=1;i<=N;i++) scanf("%d", &a[i]);
89         int ans = getCnt(), x = ans;
90         for(int i=1;i<N;i++)
91         {
92             x = x + N - 2 * a[i] - 1;
93             ans = MIN(ans, x);
94         }
95         printf("%d\n", ans);
96     }
97     return 0;
98 }