Как решить проблему D бета-версии Codeforces № 12?

Question

Нажмите здесь, чтобы посмотреть проблему.

Я не могу найти решение лучше, чем O (n ^ 2), но при n <= 500000 это не сработает!</p>

Моя идея состоит в том, чтобы отсортировать их (красота + интеллект + богатство) и проверить любого из них с теми, кто после него.

Пожалуйста, помогите!

Answer 1

Я думаю, что вы можете решить эту проблему в O (n log n), рассматривая каждую даму как точку в 3-пространстве и вычисляя выпуклую оболочку точек (см., Например, здесь ). Тогда любая точка внутри корпуса является потенциальным случаем самоубийства.

Answer 2

Если вы ограничите задачу двумя атрибутами (например, только B_i и R_i, только для целей иллюстрации), вы можете рассматривать эти атрибуты как точки на 2D-плоскости. Для каждой точки (соответствующей леди) вам нужно посчитать количество точек в (полубесконечном) прямоугольнике «справа и выше» данной точки.

Я думаю, что решение быстрее, чем O(n^2) будет включать дерево диапазонов , хотя я не думал о деталях. Смотрите также иллюстрацию здесь .

РЕДАКТИРОВАТЬ : и вы сохраняете (или обновляете при построении) количество точек «ниже» каждого узла с узлом, чтобы вы могли, например, легко получить количество точек ниже или выше точки разделения данного узла.