[BZOJ3295/Luogu3157][CQOI2011]动态逆序对(CDQ分治)

发布于 2018-04-08  6 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3295/Luogu3157][CQOI2011]动态逆序对(CDQ分治)

Description

对于序列A,它的逆序对数定义为满足i< j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Tag

CDQ分治

解决思路

给每一个数赋上一个时间戳Tim[i],第一个删除的数时间戳最大,然后依次递减,这样转化为一个偏序问题。
删除一个数i,减去的逆序对个数有两种,一种是对于j< i且A[i]< A[j]并且Tim[j]< Tim[i],另一种是对于j>i,A[i] >A[j]并且Tim[j]< Tim[i],这个可以用CDQ分治解决。
在外面对tim排序,然后分治,保证左边的tim一定小于右边。先递归左右两边,回来后保证左右分别按照在原数列中的位置(下面称作编号)排序。然后对右边的每一个数计算两次,第一次计算左边的编号小于它而值大于它的,第二次计算左边编号大于它而值小于它的,这个可以分别用树状数组做。
最后返回上一层的时候,把左右区间按照编号归并排序

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3295/Luogu3157][CQOI2011]动态逆序对(CDQ分治)


HNCJ OIer 一枚