HDU.1394 Minimum Inversion Number (线段树 单点更新 区间求和 逆序对)

题意分析

给出n个数的序列,a1,a2,a3……an,ai∈[0，n-1]，求环序列中逆序对最少的个数。

前置技能

环序列

还

线段树的逆序对求法

1. 逆序对：ai > aj 且 i < j ，换句话说数字大的反而排到前面（相对后面的小数字而言）
2. 环序列：把第一个放到最后一个数后面，就是一次成环，一个含有n个元素序列有n个环序列。
3. 线段树的逆序对求法：每个叶子节点保存的是当前值数字的个数。根据给出的数字，我们一次放入线段树，在放入的时候，其实考虑的是，当前线段树中比该数字大的数字个数有多少，这可以通过查询操作完成。然后我们放入线段树，每次都进行这样的操作，就可以得出一个序列的，逆序对个数。

每次进行成环的时候，就不用这么考虑了，对于一个序列，我们假设共有n个数字，并且当前的逆序对个数为k，对于第一个数字a，有t个数字小于a，可以计算得出有n-t-1个数字大于a。所以当我们把数字a移动到序列末端的时候，比他小的都成为了逆序对，比他大的都不是逆序对，此时的逆序对数目为k-t+n-t-1。

恰好此题中x[i]的值就是比他小的数字的个数，如此就可以通过简单循环完成。

代码总览

#include <bits/stdc++.h>

#define maxn 200010

#define NumMax 5000

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

int Sum[maxn<<2],Lazy[maxn<<2];

int x[maxn];

int N;

void PushUp(int rt){

    Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];

}

void Build(int l,int r,int rt){

    if(l==r) {

        Sum[rt] = 0;

        return;

    }

    int m=(l+r)>>1;

    Build(l,m,rt<<1);

    Build(m+1,r,rt<<1|1);

    PushUp(rt);

}

void UpdatePoint(int L,int l,int r,int rt){

    if(l==r){

        Sum[rt]++;

        return;

    }

    int m=(l+r)>>1;

    if(L <= m) UpdatePoint(L,l,m,rt<<1);

    else UpdatePoint(L,m+1,r,rt<<1|1);

    PushUp(rt);

}

void PushDown(int rt,int ln,int rn){

    if(Lazy[rt]){

        Lazy[rt<<1] = Lazy[rt];

        Lazy[rt<<1|1] = Lazy[rt];

        Sum[rt<<1] = Lazy[rt]*ln;

        Sum[rt<<1|1] = Lazy[rt]*rn;

        Lazy[rt]=0;

    }

}

void UpdateInterval(int L,int R,int C,int l,int r,int rt){

    if(L <= l && r <= R){

        Sum[rt] = C*(r-l+1);

        Lazy[rt] = C;

        return ;

    }

    int m=(l+r)>>1;

    PushDown(rt,m-l+1,r-m);

    if(L <= m) UpdateInterval(L,R,C,l,m,rt<<1);

    if(R >  m) UpdateInterval(L,R,C,m+1,r,rt<<1|1);

    PushUp(rt);

}

int Query(int L,int R,int l,int r,int rt){

    if(L <= l && r <= R){

        return Sum[rt];

    }

    int m = (l+r)>>1;

    PushDown(rt,m-l+1,r-m);

    int ANS = 0;

    if(L <= m) ANS += Query(L,R,l,m,rt<<1);

    if(R > m) ANS += Query(L,R,m+1,r,rt<<1|1);

    return ANS;

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(scanf("%d",&N)!=EOF){

        int sum = 0;

        Build(0,N-1,1);

        for(int i = 0;i<N;++i){

            scanf("%d",&x[i]);

            sum+= Query(x[i]+1,N-1,0,N-1,1);

            UpdatePoint(x[i],0,N-1,1);

        }

        int ans = sum;

        for(int i = 0;i<N;++i){

            sum = sum+N-2*x[i]-1;

            ans = min(sum,ans);

        }

        printf("%d\n",ans);

    }

    return 0;

}