hdoj 1394 Minimum Inversion Number【线段树求逆序对】

逃离我推掉我的手 2022-08-11 03:59 39阅读 0赞

求逆序对有很多算法，这里说一下线段树求逆序对的思想。

知识点：线段树，逆序对，单点更新，成段求和

算法：线段树求逆序数的前提条件是要离散化，变成连续的点，首先建树，每个节点设置一个num值为0.

然后根据逆序对的定义，前面出现过的比当前数大的个数的和，我们需要求前面的比他大的数，其实就相当于从当前a【i】点对他后面所有出现过的数求和一次。然后把当前点的值在线段树叶子节点变为1，表示出现过，并向上更新到线段树里面。比如说样例4 2 1 5 3

首先4后面没有值，4更新为1,4--5区间更新为1,1--5区间更新为1，

然后2，求3--5区间的和为1，然后把2更新为1,1--2更新为1,1---5更新为2

然后1，求2--5区间和为2，然后把1更新为1，1--2更新为2,1---5更新为3

然后5，求5---5区间和为0，然后把5区间更新为1,4--5区间更新为2,1---5区间更新为4

然后3，求4--5区间和为2.

然后把所有的和相加1+2+2 = 5，就是逆序对的个数，最简单的线段树运用。

对于当前这个题目，要求数组是环形的，可以从任一点开始，求一个最小的逆序数。

那么我们考虑对于当前一个元素移动到后面，它相当于上次求得的逆序数减去比它小的元素a【i】-1，然后加上比他大的元素n-a【i】-1，所以可以枚举求出一个最小值。

代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 101000;
    int a[N];
    struct Node
    {
        int l,r,num;
    };
    Node tree[4*N];
    void build(int l,int r,int o)
    {
        tree[o].l=l,tree[o].r=r;
        tree[o].num=0;
        if(l==r)
            return ;
        int mid=(l+r)>>1;
        build(l,mid,o<<1);
        build(mid+1,r,o+o+1);
    }
    void update(int t,int o)
    {
        if(tree[o].l==tree[o].r && tree[o].l==t)
        {
            tree[o].num++;
            return ;
        }
        int mid=(tree[o].l+tree[o].r)>>1;
        if(t>mid)
            update(t,o+o+1);
        else
            update(t,o+o);
        tree[o].num=tree[o+o].num+tree[o+o+1].num;
    }
    int query(int l,int r,int o)
    {
        if(tree[o].l==l && tree[o].r==r)
        {
            return tree[o].num;
        }
        int mid=(tree[o].l+tree[o].r)>>1;
        if(r<=mid)
            return query(l,r,o+o);
        else if(l>mid)
            return query(l,r,o+o+1);
        else
            return query(l,mid,o*2)+query(mid+1,r,o*2+1);
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++){
                scanf("%d",&a[i]);
                a[i]++;
            }
            build(1,n,1);
            int ans=0;
            for(int i=0;i<n;i++)
            {
                ans+=query(a[i],n,1);
                update(a[i],1);
            }
            int sum=ans;
            for(int i=0;i<n;i++)
            {
                sum+=n-a[i]-a[i]+1;
                //printf("%d\n",sum);
                ans=min(ans,sum);
            }
            printf("%d\n",ans);
        }
        return 0;
    }