Изменения

Тут все сложнее. Представим, что мы ищем <tex>y_1</tex> и <tex>y_2</tex> (из запроса) в PST как в обычном дереве поиска по <tex>y</tex>. Рассмотрим все точки, которые лежат между двумя путями поиска. Среди них рассмотрим точки с <tex>x <= x_q</tex>. Ровно эти точки и есть ответ. Разобьем все вершины на три группы. Первая {{---}} вершины, которые лежат хотя бы на одном из двух путей. Их <tex>O(\log\,n)</tex>. Вторая {{---}} вершины, которые находятся между двумя путями. Третья {{---}} все остальные. Время обработки вершин первой группы не превышает <tex>O(\log\,n)</tex>. Как только мы зашли в вершину третей группы, сразу поймем, что отрезок по <tex>y</tex> не пересекается с запросом и выйдем. А зайти в них мы можем только из вершин, которые лежат на двух путях (а их <tex>O(\log\,n)</tex>). Отлично! Зайдя в вершину второй группы, мы либо ее добавим в ответ и продолжим, либо выйдем, так как единственная причина, почему корень не подошел {{---}} его <tex>x</tex> слишком большой, а, значит, и все вершины поддерева не подходят. В итоге их обработка занимает <tex>O(k)</tex>. В сумме все хорошо!

}}

<code>

struct PST

== Причем тут пересечение прямоугольника с множеством прямоугольников? ==

Задача решается следующим образом. Будем находить ответ тремя разными способами, а их объединение и будет настоящим ответом. Будем считать, что объединение множеств можно делать за <tex>O(n)</tex>, где <tex>n</tex> {{---}} суммарное количество элементов в них.