hdu1394 Minimum Inversion Number

http://acm.hdu.edu.cn/showproblem.php?pid=1394
线段树，单点更新
用线段树优化，求逆序数，O（N＊logN）
 1 #include <stdio.h>
 2 
 3 #define lson l, m, root<<1
 4 #define rson m+1, r, root<<1|1
 5 
 6 const int maxn = 5010;
 7 int sum[maxn<<2];
 8 
 9 void push_up(int root)
10 {
11     sum[root] = sum[root<<1] + sum[root<<1|1];
12 }
13 
14 void build(int l, int r, int root)
15 {
16     int m;
17     if(l == r)
18     {
19         sum[root] = 0;
20         return;
21     }
22     m = (l + r) >> 1;
23     build(lson);
24     build(rson);
25     push_up(root);
26 }
27 
28 void update(int x, int one, int l, int r, int root)
29 {
30     int m;
31     if(l == r)
32     {
33         sum[root] = one;
34         return;
35     }
36     m = (l + r) >> 1;
37     if(x <= m)
38     {
39         update(x, one, lson);
40     }
41     if(m+1 <= x)
42     {
43         update(x, one, rson);
44     }
45     push_up(root);
46 }
47 
48 int query(int L, int R, int l, int r, int root)
49 {
50     int m, result;
51     if(L <= l && r <= R)
52     {
53         return sum[root];
54     }
55     result = 0;
56     m = (l + r) >> 1;
57     if(L <= m)
58     {
59         result += query(L, R, lson);
60     }
61     if(m+1 <= R)
62     {
63         result += query(L, R, rson);
64     }
65     return result;
66 }
67 
68 int main()
69 {
70     int n, a[maxn], i, sum, result;
71     while(~scanf("%d", &n))
72     {
73         build(1, n, 1);
74         sum = 0;
75         for(i=1; i<=n; i++)
76         {
77             scanf("%d", a+i);
78             a[i] ++;
79             sum += query(a[i], n, 1, n, 1);
80             update(a[i], 1, 1, n, 1);
81         }
82         //printf("%d\n", sum);
83         result = sum;
84         for(i=1; i<=n-1; i++)
85         {
86             //printf("%d + %d == ", sum, n-1-(a[i]-1)*2);
87             sum += (n-1-(a[i]-1)*2);
88             //printf("%d\n", sum);
89             if(sum < result)
90             {
91                 result = sum;
92             }
93         }
94         printf("%d\n", result);
95     }
96     return 0;
97 }