【DS】线段树HDU-1394

客官°小女子只卖身不卖艺 2021-12-05 13:11 221阅读 0赞

/* 
     * File:   main.cpp
     * Author: lenovo
     *
     * Created on 2011年9月29日, 上午10:08
    */
    
    #include <cstdlib>
    #include <cstdio>
    #include <iostream>
    using namespace std;
    
    /*用线段树求逆序数的思想
     * 
    */
    #define lson l , m , rt << 1
    #define rson m+1 , r , rt << 1 | 1
    
    const int maxn = 5050;
    int sum[maxn << 2];//统计出现的次数
    int num[maxn];
    
    void pushup(int rt)
    {
        
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    
    void build(int l , int r , int rt)
    {
        
        sum[rt] = 0;
    if(l == r)
    return ;
    int m = (l+r) >> 1;
        build(lson);
        build(rson);
    }
    
    void update(int p , int l , int r , int rt)
    {
        
    if(l == r)
        {
        
            sum[rt]++;
    return;
        }
    int m = (l+r)>>1;
    if(p <= m)
            update(p,lson);
    else
            update(p,rson);
        pushup(rt);
    }
    
    int query(int L , int R , int l , int r , int rt)//统计比L大的数出现过多少个,这样逆序数就增加多少个
    {
        
    if(L <= l && r <= R)
    return sum[rt];
    int m = (l+r)>>1;
    int res = 0;
    if(L <= m)
            res += query(L , R ,lson);
    if(R > m)
            res += query(L , R , rson);
    return res;
    }
    
    
    int main(int argc, char** argv) {
        
    int n , i , ini_num;
    while(scanf("%d",&n) != EOF)
        {
        
            build(0,n-1,1);
            ini_num = 0;
    for(i = 0 ; i < n ; i++)
            {
        
                scanf("%d",&num[i]);
                ini_num += query(num[i],n-1,0,n-1,1);//进行统计
                update(num[i],0,n-1,1);//同济完后把num[i]插入到序列的最后
            }
    int res = ini_num;
    for(i = 0 ; i < n ; i++)
            {
        
                ini_num = ini_num - num[i] + (n-1-num[i]);
                res = min(ini_num,res);
            }
            printf("%d\n",res);
        }
    return 0;
    }

转载于:https://www.cnblogs.com/zuckerTT/archive/2011/09/29/2195336.html