UVALive 5871 Arnooks

UVALive 5871 Arnooks’s Defensive Line (CDQ分治)

在我们平常使用的分治中,每一个子问题只解决它本身(可以说是封闭的)。 而在cdq分治中,对于划分出来的两个子问题,前一个子问题用来解决后一个子问题而不是它本身。 具体算法流程如下: 1.将整个操作序列分为两个长度相等的部分(分) 2.递归处理前一部分的子问题(治1) 3.计算前一部分的子问题中的修改操作对后一部分子问题的影响(治2) 4.递归处理后一部分子问...
08月14日 42
HDU 5919 Sequence II (主席树)

HDU 5919 Sequence II (主席树)

题目链接:点我~~ 题意:给定一个序列n,有m次查询,每次查询一个区间[l,r],求区间中每一种数在区间中第一次出现的位置的中位数,强制在线。 思路: 主席树维护后缀[i,n],然后对于每次碰到一个数字,就把它以前的位置−1,新位置+1 主席树维护区间不同数字的个数k 然后寻找区间第k/2大呗 因为是维护的后缀,直接找root[l]里的第k/2大出现的位置就...
10月04日 191
显示更多
  1. .01
  2. .02