[洛谷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] ,但整型范围很大,不可能开这么大的数组,所以我们只需要保留它们的相对大小,用离散化处理。

代码

发表评论

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