hdu1394 Minimum Inversion Number-白红宇

hdu1394 Minimum Inversion Number

阅读量：6845 次

发布时间：2019-06-26

本文共 1367 字，大约阅读时间需要 4 分钟。

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

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
          5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 using namespace std;10 #define lson l , m , rt << 111 #define rson m + 1 , r , rt << 1 | 112 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