BZOJ 4066 简单题(K-D Tree)解题报告


解题思路

本题是要求实现对点更新和矩形区域的查询操作,强制在线。于是很容易和 K-D Tree 的按区域管辖和合并的性质联系到一起。本题需要对在矩形内外的判断细心留意,以免出错。

另外由于本题大量的插入操作,K-D Tree 可能随着数据量增大导致结构不平衡,从而影响效率。因此这里我们需要用到类似替罪羊树的思想,引入一个平衡因子(这里我设置了 0.7),一旦某一侧子树的 size 过大(所占比例超过平衡因子规定的临界值),就重建这颗树,以此来保证效率。当然直接按插入次数暴力重建整棵树也是可以的。


HDU 5992 Finding Hotels(K-D Tree)解题报告


解题思路

2016 ICPC 青岛 的一道金牌题,是 K-D Tree 的典型应用。

我们可以按 x, y, c 建立三维 K-D Tree,查询的时候如果 c 过大,则直接把当前搜到的 dis 设置为 INF,其他操作和普通 K-D Tree 基本一致。

另外应注意,如果直接使用输入时的数组 Build,可能会被 nth_element() 打乱顺序,因此更新答案时需要记录原数组中的下标信息。


Codeforces 869E The Untended Antiquity(二维树状数组)解题报告


解题思路

很巧妙的一道题。我们可以考虑用二维树状数组去做,新建障碍视为在二位数组中对一个矩形区域增加一个值,而移除障碍就是减掉这个值,查询就是判断两个点的值是否一致。

那么问题来了,这个值要加多少呢?这个题给了很巧妙的做法,就是每次随机一个数(可以去 Editorial 看一下证明)。当然其他不会导致重复的生成方式也是可以的。


HDU 5919 Sequence II(主席树)解题报告


解题思路

2016 CCPC 长春的一道银牌题,要求强制在线。用过主席树求区间第 K 大以及区间不同数个数的话基本就是一眼题了,比以前不会主席树的时候用的分块做法不知道高到哪里去了。

按照求区间不同数的做法建树,查询时先查出区间内不同数的个数,除以 2 得到一个数 k,用这个 k 在区间 [l, n] 内查询第 k 大即是题目中询问的中位数。