Я пытался решить эту алгоритмическую задачу и наткнулся на это прекрасное решение:
«Идея состоит в том, чтобы обрабатывать ai, bi и ci асимметрично. BIT поддерживает минимальные запросы для ключевых интервалов, начинающихся с 1. Мы используем ci в качестве значений и bi в качестве ключей. Они вставляются в порядке возрастания ai. Таким образом, для каждого a i, в свою очередь, структура данных позволяет запрашивать наименьшее значение cj (возможно, ∞) для bj в [1..b i) и aj ‹ ai. Имеем cj ‹ ci > тогда и только тогда, когда участник i не отличник».
Теперь мне трудно понять это решение.
Вот что я понимаю об этом решении: я знаю, что двоичное индексированное дерево используется для ответов на такие запросы, как нахождение суммы интервалов в массиве, а также поддерживает обновления в элементах. Он выполняет обе операции с временной сложностью O (logn) каждая. Теперь это решение говорит о том, что мы строим BIT с ключами как ci и значением как bi, то есть в основном bi является дополнительным значением это идет с каждым узлом. Теперь мы вставляем элементы в дерево с возрастающими значениями ai, здесь я потерял хватку. Какая разница, в каком порядке мы вставляем узлы и что говорит оператор после этой части, я понятия не имею.
Пожалуйста, помогите мне понять, что говорит это решение.