[洛谷P1908]逆序对

题目

题目描述

猫猫TOM和小老鼠JERRY最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。最近,TOM老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中ai>aj且i<j的有序对。知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

输入格式

第一行,一个数n,表示序列中有n个数。
第二行n个数,表示给定的序列。

输出格式

给定序列中逆序对的数目。

输入样例

输出样例

说明

对于50%的数据,n≤2500
对于100%的数据,n≤40000。

题解

树状数组

既然名字都叫树状数组,那么肯定是和数有关的咯,我们来先看一个二叉树

二叉树

我们来稍微变下形

变形

现在我们把树状数组c[]摆放到每一列的顶端

顶端

C[i]代表子树的叶子结点的权值之和
我们通过这张图可以知道
$$ C[1]=A[1]; $$
$$ C[2]=A[1]+A[2]; $$
$$ C[3]=A[3]; $$
$$ C[4]=A[1]+A[2]+A[3]+A[4]; $$
$$ C[5]=A[5]; $$
$$ C[6]=A[5]+A[6]; $$
$$ C[7]=A[7]; $$
$$ C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]; $$
通过分情况讨论好像是有什么规律,那有没有更一般的规律呢?
我们不妨将树状数组的编号转换成二进制看看
二进制
$$ 1=(001)---C[1]=A[1]; $$
$$ 2=(010)---C[2]=A[1]+A[2]; $$
$$ 3=(011)---C[3]=A[3]; $$
$$ 4=(100)---C[4]=A[1]+A[2]+A[3]+A[4]; $$
$$ 5=(101)---C[5]=A[5]; $$
$$ 6=(110)---C[6]=A[5]+A[6]; $$
$$ 7=(111)---C[7]=A[7]; $$
$$ 8=(1000)---C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]; $$

对照式子可以发现 C[i]=A[i-2^k+1]+A[i-2^k+2]+......A[i]; (k为i的二进制中从最低位到高位连续零的长度)例如i=8时,k=3。

而lowbit(x)函数的作用就是取出x的最低位。

树状数组的优点在于单点更新以及区间查询,对于求逆序对来说,知道一个数的位置x,那么1~x范围内就是比它小的数,而用已经插入的数的个数减去这个数,累加起来就是我们要算的逆序对数。

离散化

上面提到我们要知道一个数的位置,可以用树状数组下标来表示$ c[x] $,但整型范围很大,不可能开这么大的数组,所以我们只需要保留它们的相对大小,用离散化处理。

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注