杭电oj 1394 线段树求逆序数Minimum Inversion Number题解：线段树求解逆序数并求出多个逆序的最小值因为数据范围是 0 ~n-1 所以不需要进行离散化可以直接运用线段树求解

72 阅读 0 评论 48 点赞

我是靠谱客的博主英俊春天，最近开发中收集的这篇文章主要介绍杭电oj 1394 线段树求逆序数Minimum Inversion Number题解：线段树求解逆序数并求出多个逆序的最小值因为数据范围是 0 ~n-1 所以不需要进行离散化可以直接运用线段树求解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Minimum Inversion Number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24244 Accepted Submission(s): 14354

Problem Description

The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.

Output

For each case, output the minimum inversion number on a single line.

Sample Input

10 1 3 6 9 0 8 5 7 4 2

Sample Output

题解：线段树求解逆序数并求出多个逆序的最小值因为数据范围是 0 ~n-1 所以不需要进行离散化可以直接运用线段树求解

假设已知第一个序列的逆序数为ans 则下一个序列的逆序数为 ans - 2 * a[i] + n + 1个逆序数

因为假设当前第一个值为a[i] , 总共n个数。则在当前序列有(n-a[i])个数字比当前值大，有（a[i] - 1）个数比当前值小当该数挪到最后，则新增加n-a[i]个逆序对并且减少了 a[i] - 1个逆序对所以新的逆序对的数量就是 ans + n - a[i] - (a[i] - 1) = ans + n - 2 * a[i] + 1;

ac代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5010;
struct Node{
    int l, r, sum;
}Tree[maxn * 4];

void push_up(int k)
{
    Tree[k].sum = Tree[k<<1].sum + Tree[k<<1|1].sum;
}

void build(int k, int l, int r)
{
    Tree[k].l =l, Tree[k].r = r;
    if(l == r)
    {
        Tree[k].sum = 0;
    }
    else
    {
        int mid = (l + r) >> 1;
        build(k<<1, l, mid);
        build(k<<1|1,mid+1, r);
        push_up(k);
    }
}

void updata(int k, int l, int r, int val)
{
    int L = Tree[k].l, R = Tree[k].r;
    if(l <= L && R <= r)
    {
        Tree[k].sum += 1;
    }
    else
    {
        int mid = (L + R) >> 1;
        if(l <= mid)
            updata(k<<1, l, r, val);
        if(mid < r)
            updata(k<<1|1, l, r, val);
        push_up(k);
    }
}

int query(int k, int l, int r)
{
    int L = Tree[k].l, R = Tree[k].r;
    if(l <= L && R <= r)
    {
        return Tree[k].sum;
    }
    else
    {
        int tmp_sum = 0;
        int mid = (L + R) >> 1;
        if(l <= mid)
            tmp_sum += query(k<<1, l, r);
        if(mid < r)
            tmp_sum += query(k<<1|1, l, r);
        return tmp_sum;
    }
}

int main()
{
    int n;
    while(cin >> n)
    {
        build(1,1,n);
        vector<int> a(n);
        for(int i = 0; i<n; i++)
        {
            cin >> a[i];
            a[i]++;
        }
        int ans = 0;
        for(int i = 0; i<n; i++)
        {
            updata(1,a[i],a[i],1);
            ans += i + 1 - query(1,1,a[i]);
        }
        int tmp_min = 0x3f3f3f3f;
        for(int i = 0; i<n; i++)
        {
            ans = ans - 2 * a[i] + n + 1;
            tmp_min = min(tmp_min, ans);
        }
        cout<<tmp_min<<endl;
    }
    return 0;
}