hdu1394 Minimum Inversion Number

题意:求Inversion后的最小逆序数
思路:用O(nlogn)复杂度求出最初逆序数后,就可以用O(1)的复杂度分别递推出其他解
线段树功能:update:单点增减 query:区间求和
这里做了一点修改，就是，把操作抽象出来了。
详细请见代码：

View Code

 1 #include<iostream>
 2 #include<string>
 3 #include<queue>
 4 #include<map>
 5 #include<stack>
 6 #include<cmath>
 7 #include<functional>
 8 #include<algorithm>
 9 using namespace std;
10 #define lson l , m , rt << 1
11 #define rson m + 1 , r , rt << 1 | 1
12 const int maxn = 5500;
13 int sum[maxn<<2];
14 int n;
15 
16 int operate(int a,int b){
17     return a+b;
18 }
19 
20 
21 void PushUp(int rt){
22     sum[rt]=operate(sum[rt<<1],sum[rt<<1|1]);
23 }
24 
25 void bulid(int l=1,int r=n,int rt=1){
26     if(l==r){
27         sum[rt]=0;return ;
28     }
29     int m=(l+r)>>1;
30     bulid(lson);
31     bulid(rson);
32     PushUp(rt);
33 }
34 
35 void update(int p,int add=1,int l=1,int r=n,int rt=1){
36     if(l==r){
37         sum[rt]+=add;return ;
38     }
39     int m=(l+r)>>1;
40     if(p<=m)update(p,add,lson);
41     else update(p,add,rson);
42     PushUp(rt);
43 }
44 
45 int query(int L,int R,int l=1,int r=n,int rt=1){
46     if(L<=l && r<=R){
47         return sum[rt];
48     }
49     int m=(l+r)>>1;
50     int ans=0;
51     if(L<=m)ans=operate(ans,query(L,R,lson));
52     if(R> m)ans=operate(ans,query(L,R,rson));
53     return ans;
54 }
55 
56 
57 int main(){
58     
59     int tmp[maxn];
60     while(~scanf("%d",&n)){
61         bulid();
62         int sum=0;
63         for(int i=0;i<n;i++){
64             scanf("%d",&tmp[i]);tmp[i]++;
65             sum+=query(tmp[i],n);
66             update(tmp[i]);
67         }
68         int ret=sum;
69         for(int i=0;i<n;i++){
70             sum+=n-(tmp[i]<<1)+1;
71             ret=min(ret,sum);
72         }
73         printf("%d\n",ret);
74         
75     }
76 
77     return 0;
78 }