Нам дают n студентов с оценками cgpa (колледж) и jee (ранг в вступительном экзамене) каждого студента.
Для каждого учащегося мы должны рассчитать количество учеников, которые имеют более высокий рейтинг качества, но худший рейтинг джи.
(x1, y1), (x2, y2) ... (xi, yi) ... (xn, yn)
для каждого я, мы должны рассчитать нет. из j, для которых xj> xi и yj> yi (худший ранг означает больший ранг.)
Я мог бы придумать следующий алгоритм nlogn-
Сортировать их по убыванию cgpa.
Теперь начните сканирование слева.
Сохраняйте отсканированные до сих пор ученики в сбалансированном бинарном дереве (в соответствии с их рангом джи).
Для следующего ученика просто выясните число учеников, уже отсканированных с большим рангом, запросив сбалансированное двоичное дерево.
Я не знаю, как поддерживать сбалансированный BST, в котором я могу вернуть нет. элементов меньше k в O (logn). Нам нужно поддерживать нет. узлов в поддереве на каждом узле. Но как это сделать?
Либо помогите с вышеуказанным, либо предоставьте другой алгоритм, возможно, DP.