Click here to view the problem.
我无法找到比 O(n^2) 更好的解决方案，但是当 n<=500000 时，这是行不通的!
我的想法是按(美貌+智力+丰富)对它们进行排序，然后用它后面的任何一个进行测试。
请帮忙!
最佳答案
如果将问题限制在两个属性上(例如，只有 B_i 和 R_i，仅用于说明目的)，您可以将这些属性视为 2D 平面中的点.对于每个点(对应于一位女士)，您必须计算给定点“右上方”的(半无限)矩形中的点数。
我认为比 O(n^2) 更快的解决方案将涉及 range tree虽然我没有想过细节。另见插图 here .
编辑:并且您将存储(或在构建时更新)每个节点“下方”的节点数，这样您就可以，例如轻松获取给定节点 split 点以下或以上的点数。
关于c++ - 我如何解决 Codeforces Beta 第 12 轮问题 D？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3866441/