Hdu1394 Minimum Inversion Number 线段树求逆序数详细解题报告
温柔似野鬼°
643次浏览
2021年01月26日 19:36
最佳经验
本文由作者推荐
-
Hdu1394 Minimum Inversion Number
/*
Name: hdu1394
解题报告
Copyright: ecjtu_acm
训练基地
Author: yimao
Date: 09-08-10 20:47
Description:
线段树求逆序数
*/
一、题目
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
16
二、题目大意及分析
给定一个序列，对该序列的
n
种排列（排列如 下）的每种排列的逆序数求最大值：
1
a1, a2, ..., an-1, an
a2, a3, ..., an, a1
a3, a4, ..., an, a1, a2
...
an, a1, a2, ..., an-1
当初做这一题，花了好多时间，百度了好多 ，也问了学长，初看下面的代码看不懂，几天后
再细看，终于弄懂了，同时自己写了个暴利的代码也过了 ，先说一下暴力的方法，
再好过渡
到线段树的做法。
输入数组时 ，每输入一个数，就
for(j=0;j
sum
把逆序数
统计出来，
其实这里才是暴力，
至于后面的就很巧妙，公式很容易推 出，因为题目总是把第
一个数移到最后一个位置，
所以原来比它小的数
（和它构成逆序 ）
在移动之后就不是逆序了，
而原来比它大的数（不和它构成逆序）在移动之后就是逆序了，这 样
sum
就变化了：
Sum=sum-(low[a[i]])+(up[a[i]]);
显然在序列
0,1,2,
…
..n-1
中
比
a[i]
小的数的个数是
Low[a[i]]=a[i];
比
a[i]
大的数的个数是
up[a[i]]=n-a[i]-1;
题目要求是循环移动
n
次，那么只要写个
for
，把a[0],a[1],a[2]
……
a[n-1]
都移动一
遍，
sum
进行
n
次上面的公式运算，同时记录最小值，就是最小逆序数了。
有了上面的说明，写暴力的代码（见下面）就很简单了。
那么接下来就是过渡到线段树了。
发现上面分两部分，第一是统计初始的逆序数，第 二是按顺序循环移动
n
个值，在第二部
分是
O(n)
时间，无法再优 化了。那么关键是就是第一部分的优化，刚开始我没看太懂别人
的代码，后来才醒悟过来，这题说是用线 段树做，
其实仅是统计第一次的逆序数时用到，那
么线段树统计这第一次的逆序数思想是这样的 ：
先建一个空树；
逐个插入值（即输入的一个值）；
在每插入一个值后就更新包含该区间的所有的数的个数（加一）。
为什么可以这样呢，下面引用一个人的说明：
（
The flowering information is from gongshaoqing:
）
线段树求逆序数
3 2 5 4 6 1
插入
3
时
询问
3-6
之间元素的个数
v1=0
插入
2
时
询问
2-6
之间元素的个数
v2=1
.
. v6=6
累加
v1
……
v6 =sum
2
再详细点，举个例子，插入
2
的时候，你要的找的数肯定是比
2
大的数的个数（当然是已
经插进来了的，就是序列里排在
2
前面的 ），这时候发现只有
3
比
2
先被插入到树中（且
只有
3而已）
，
那么
2
由
2
产生的逆序数就是
1了，
累加到
sum
中；
之后更新，
update(2,1),< br>把包含
2
的所有区间的数的个数都
+1
，便于之后的
1
，
0
，去查找。
完毕。
三、代码及相关分析
/*
94
袁传顺
46MS
264K
1483B
C++
2010-08-09 16:20:16
*/
//P.S.
写法不同，跑的时间不同，下面是网上搜来的，提交情况如上
,
//
我在下面加了些注释，自己的代码就不公布了
.
#include
#include
#define LL(x) ((x)<<1) //
两倍；
#define RR(x) ((x)<<1|1) //
两倍
+1
；
using namespace std;
struct Seg_Tree {
int left,right,val;
int calmid() {
return (left+right)/2;
}
}tt[15000];
int val[5001];
void build(int left,int right,int idx) {
tt[idx].left = left;
tt[idx].right = right;
tt[idx].val = 0;
if(left == right) return
int mid = tt[idx].calmid();
build(left,mid,LL(idx));
build(mid+1,right,RR(idx));
}
//< br>查询
[left
，
right]
中数的个数，不要把
left
，
right
看作序号，要看做数；
3