HDU 1394 Minimum Inversion Number(单点更新)

题目链接

题目分析

1、题目要求输入一个整数n(n<=5000)，随后输入n个数，这n个数是0~n-1的全排列

2、对于这组序列，可以做一些变换，把前面的m(m>=0)个数放到序列的最后

3、对于所有的变换后的序列，求个数最少的逆序对是多少

实现方法

1、线段树

2、首先建立一颗空树，树根为1，所有的结点的值都是0

3、每输入一个数，对线段树进行单点更新，更新之后逆序对数也要改变

• 如果输入的数a[i]不等于n-1，那就只需查看从a[i]+1~n-1之间已经输入过的数有多少个
• 这么理解：如果a[i]+1~n-1之间的a[j]已经输入过了，那么毫无疑问a[j]>a[i]，且a[j]先于a[i]加入树家庭，说明这就是一个a[i] < a[j]（j>i）是一个逆序对

4、在求出m=0（即初始状况下的逆序对数）后，就开始求变换后的序列的逆序对

• 简单啊，线段树不需要更新了，只需要每次把第一位放序列最后，循环n次。
• 这么理解：把第一个数放在序列最后面，那么逆序对数会增加也会减少，增加的是从2~n-1之间大于a[1]的个数（即n-1-a[1]），减少的是2~n-1之间小于a[1]的个数（即a[i]）

最好画出线段树，单点一个一个的更新、查询尝试

AC代码

#include<iostream>
using namespace std;

const int N = 5000+5;

int a[N];

struct node{
    int l;
    int r;
    int v;
    int m(){
        return (l+r)/2;
    }
};

struct Seg{
    node tree[N*4];
    void build(int i,int l,int r){
        tree[i].l = l;
        tree[i].r = r;
        tree[i].v = 0;
        if(l != r){
            int m = tree[i].m();
            build(i*2,l,m);
            build(i*2+1,m+1,r); 
        }
    }

    void update(int p,int i){
        int l = tree[i].l;
        int r = tree[i].r;
        if(l==r) tree[i].v ++ ;
        else{
            int m = tree[i].m();
            if(p<=m) update(p,i*2);
            else update(p,i*2+1);
            tree[i].v = tree[i*2].v + tree[i*2+1].v; 
        }
    }

    int query(int i,int l,int r){
        int li = tree[i].l;
        int ri = tree[i].r;
        if(l<=li && ri<=r) return tree[i].v;
        else{
            int m = tree[i].m();
            int s1 = 0;
            int s2 = 0;
            if(l<=m) s1 = query(i*2,l,r);
            if(r>m) s2 = query(i*2+1,l,r);
            return s1+s2;
        }
    }
}seg;

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int sum=0;
        seg.build(1,0,n-1);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            seg.update(a[i],1);
            if(a[i]!=n-1) sum+=seg.query(1,a[i]+1,n-1);
        }
        int mi = sum;
        for(int i=1;i<=n;i++){
            sum-=a[i];
            sum+=n-1-a[i];
            mi = min(mi,sum);
        }
        printf("%d\n",mi);
    }
    return 0;
}