如何解决Codeforces测试版round#12问题D？

Question

Click here to view the problem.

我找不到比O(n^2)更好的解决方案，但是对于n<=500000，这是行不通的！

我的想法是按照(beauty+intellect+richness)对它们进行排序，并用后面的那些来测试它们中的任何一个。

请帮帮我！

Answer 1

如果将问题限制为两个属性(例如，仅出于说明目的，仅使用B_i和R_i )，则可以将这些属性视为2D平面中的点。对于每个点(对应于一位女士)，你必须计算在给定点“右上方”的(半无限)矩形中的点数。

我认为比O(n^2)更快的解决方案将涉及range tree，尽管我还没有考虑细节。另请参阅插图here。

EDIT：你可以用节点存储(或在构建时更新)每个节点“下方”的点数，这样你就可以很容易地得到低于或高于给定节点的分割点的点数。

Answer 2

我认为你可以在O( n )中解决这个问题，方法是将每个女士视为3-空间中的一个点，并计算这些点的凸包(例如，参见here)。那么，船体内部的任何点都是潜在的自杀案例。