UVALive 5871 Arnooks

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

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

HDU 5992 Finding Hotels (KD树)

题意:给出n个宾馆的坐标以及价格,现在有m个人要住宾馆,给出了m个的坐标和他们能承受的最高价格,询问在承受价格之内的最近的宾馆的坐标和价格,如果答案不唯一,输出顺序在前的宾馆。 思路:多了价值的限制条件,在同样满足条件的情况下,优先查询编号小的 #include <bits/stdc++.h> using namespace std; typ...
02月13日 1,783
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日 2,113
显示更多
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40