高度由习惯堆积

分类 算法:CDQ分治 下的文章

BZOJ2726 SDOI2012 任务安排

题目机器上有N个需要处理的任务,它们构成了一个序列。这些任务被标号为1到N,因此序列的排列为1,2,3...N。这N个任务被分成若干批,每批包含相邻的若干任务。从时刻0开始,这些任务被分批加工,第i个任务单独完成所需的时间是Ti。在每批任务开始前,机器需要启动时间S,而完成这批任务所需的时间是各个任务需要时间的总和。注意,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系...

BZOJ 4553 [Tjoi2016&Heoi2016]序列

题目佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。注意:每种变化最多只有一个值发生变化。在样例输入1中,所有的变化是1 2 32 2 31...
December 15, 2018

动态逆序对(CDQ分治)

题目对于序列 $A$ ,它的逆序对数定义为满足 $i<j$ ,且 $Ai>Aj$ 的数对 $(i,j)$ 的个数。给定 $1$ 到 $n$ 的一个排列,按照某种顺序依次删除 $m$ 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。思路1我们反向来看,离线询问,将问题转变成一个一个往序列中加入元素。接着很容易发现这是一道三元组的题目,对于两个数来说,必须在满足题目条...