需要的前置技能

• 线段树（权值线段树）
• 离散化

常见应用

• 区间/树上路径第 K 大
• 区间不同数的个数

简介

Codeforces Rating System 是著名算法竞赛网站 Codeforces 的评分计算系统。

Codeforces 使用 rating（评分）来衡量选手水平。每个人都有一定的初始 rating。改变 rating 的主要方式为标准 Codeforces 比赛，一场比赛结束后，Codeforces Rating System 会根据所有参赛选手的现有 rating 和比赛排名来计算每位选手 rating 变化值，以体现出比赛中选手的发挥水平。

在这篇文章里，我们将介绍一下 Codeforces Rating System 的算法步骤，并给出示例代码和测试用例。如果你对 Codeforces 这类多人竞技比赛的评分机制感兴趣，本文可以成为一个参考。

解题思路

本题是要求实现对点更新和矩形区域的查询操作，强制在线。于是很容易和 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 看一下证明）。当然其他不会导致重复的生成方式也是可以的。