欢迎大家光临 bLue 的博客。

ACM 退役有两个月了，现在正默默开发和维护一些校内的 Web 项目并学习 Web 前端技术。
难得终于想起来搭博客的事情，于是便舍弃了原来的 CSDN 博客，重新搭了一个 Typecho 博客（已搬运先前全部文章），以后就在这里写博客啦！
欢迎大家收藏关注～

解题思路

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

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

解题思路

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

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

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

解题思路

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

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

解题思路

算是一道 Link/Cut Tree 的模板题了，另外也可以巩固一下 Splay 的合并信息的方法。应特别注意 PushDown 相关的计算不要出错。