[线段树]hdoj 1394

 

题意

    给出一列n个数字，每一个数字都和其他数字不同，现在每次都把第一个数挪到最后面，求这个过程中这个数列逆序数对最少有多少对。

 

思路

      先用线段树求出初始的数列逆序对数，再用第一个数列推出第二个，第三个直到第n个，输出最小的那个

      这里关键是线段树在lonn的时间复杂度内求出当前数列逆序数对的方法，每次插入一个数，num[i] ，都查询一遍在num[i]+1---n中存在多少个已经插入的点。

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 6000;
struct{
    int l,r,val;
}node[nMax*4];
int num[nMax];
void build(int l, int r, int u){    //建树
    node[u].val = 0;
    node[u].l=l;
    node[u].r=r;
    if(l == r){
        return;
    }
    int m = (l+r)/2;
    build(l , m ,u*2);
    build(m+1 , r, u*2 + 1);
}
void update(int p,int u){  //更新
    int l = node[u].l;
    int r = node[u].r;
    if(l == r){
        num[u]++;
    }else{
        int m = (l + r)>>1  ;
        if( p <= m ){
            update(p , u*2) ;
        }else{
            update (p ,u * 2 + 1) ;
        }
        num[u] = ( num[u*2] + num[u*2+1]) ;
    }
}

int query(int le ,int ri ,int u){    //查询
    int l = node[u].l;
    int r = node[u].r;
    if(le <= l && r <= ri ){
        return num[u];
    }
    int m = ( l + r ) >> 1 , res = 0 ;
    if(ri >= m + 1 ){
        res += query(le , ri  ,u * 2 + 1 );
    }
    if( le <= m ){
        res += query(le , ri , u * 2 );
    }
    return res;
}
int ipt[nMax];
int main(){
    int n , i, j ,a ,b ,c , sum ;
    while(scanf("%d",&n)!=EOF){
        sum = 0;
        memset(num , 0, sizeof(num));
        build(0 , n-1, 1);
        for(i = 0; i < n ; i++){
            scanf("%d",&ipt[i]);
            update( ipt[i] ,1);
            sum += query(ipt[i] + 1 , n-1 , 1);
        }
        int ans = sum ;
//        cout<<ans<<endl;
        for(i = 0 ;i < n ; i++ ){
            sum = sum  - 2 * ipt[i] + n -1 ;
            ans = min(ans , sum);
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax = 6000;
struct{
    int l,r,val;
}node[nMax*4];
int num[nMax];
void build(int l, int r, int u){    //建树
    node[u].val = 0;
    node[u].l=l;
    node[u].r=r;
    if(l == r){
        return;
    }
    int m = (l+r)/2;
    build(l , m ,u*2);
    build(m+1 , r, u*2 + 1);
}
void update(int p,int u){  //更新
    int l = node[u].l;
    int r = node[u].r;
    if(l == r){
        num[u]++;
    }else{
        int m = (l + r)>>1  ;
        if( p <= m ){
            update(p , u*2) ;
        }else{
            update (p ,u * 2 + 1) ;
        }
        num[u] = ( num[u*2] + num[u*2+1]) ;
    }
}

int query(int left, int right, int u){           //  查询。
    if(node[u].l == left && node[u].r == right)
        return num[u];
    if(right <= node[2*u].r)
        return query(left, right, 2*u);
    if(left >= node[2*u+1].l)
        return query(left, right, 2*u+1);
    int a = query(left, (node[u].l+node[u].r)/2, 2*u);
    int b = query((node[u].l+node[u].r)/2+1, right, 2*u+1);
    return a + b;
}
int ipt[nMax];
int main(){
    int n , i, j ,a ,b ,c , sum ;
    while(scanf("%d",&n)!=EOF){
        sum = 0;
        memset(num , 0, sizeof(num));
        build(0 , n-1, 1);
        for(i = 0; i < n ; i++){
            scanf("%d",&ipt[i]);
            sum += query(ipt[i], n-1 , 1);
            update( ipt[i] ,1);
        }
        int ans = sum ;
//        cout<<ans<<endl;
        for(i = 0 ;i < n ; i++ ){
            sum = sum  - 2 * ipt[i] + n -1 ;
            ans = min(ans , sum);
        }
        printf("%d\n",ans);
    }
    return 0;
}