1632
правки
Изменения
м
Хотел бы я знать[[Файл:PSTVIEW.png|400px|thumb|left]]Задача решается следующим образом. Будем находить ответ тремя разными способами, а их объединение и будет настоящим ответом. Будем считать, что объединение множеств можно делать за <tex>O(n)</tex>, где <tex>n</tex> {{---}} суммарное количество элементов в них.
Ну а вообще задача решается следующим образом'''Первый способ. Будем находить ответ тремя разными способами''' Найдем все прямоугольники, а их объединение и будет настоящим ответомв которых прямоугольник из запроса лежит полностью. Для этого нужно решать такую задачу. Будем считатьДано множество прямоугольников, для заданной точки найти все прямоугольники, что объединение множеств в которых она лежит. Это точно можно делать решать за <tex>O(\log^2\,n+answer)</tex>, где <tex>n</tex> {{---}} суммарное количество элементов в нихс помощью двухмерного [[Дерево интервалов (interval_tree) и пересечение точки с множеством интервалов | дерева интервалов]]. А может можно и проще.
'''Второй способ.''' Найдем все прямоугольники, которые полностью лежат внутри заданного в запросе. Для этого воспользуемся [[Перечисление_точек_в_произвольном_прямоугольнике_за_n_*_log_%5E(d_-_1)_n_(range_tree)]]. Просто для каждого прямоугольника добавим в range tree его левый верхний угол. Задав запрос в виде нашего прямоугольника, мы получим то, что и нужно. '''Третий способ.''' Найдем все прямоугольники, хотя бы одна сторона которого пересекает заданный в запросе. Для этого воспользуемся [[Пересечение_прямоугольника_с_множеством_непересекающихся_отрезков_(segment_tree)| деревом отрезков]]. В структуру добавим все стороны всех прямоугольников и зададим запрос в виде нашего прямоугольника.
rollbackEdits.php mass rollback
[[Категория: Вычислительная геометрия]]
== Определение ==
Priority Search Tree позволяет решать следующую задачу. Даны <tex>n</tex> точек, а также запросы. Каждый запрос характеризуется отрезком по одной координате <tex>[y_1, y_2]</tex>, а также числом <tex>x_q</tex> по другой координате. Для каждого запроса структура возвращает все точки, которые находятся в отрезке <tex>[y_1, y_2]</tex> по одной координате, и имеют другую координату не больше <tex>x_q</tex>. На каждый запрос дерево отвечает за <tex>O(\log\,n + k)</tex>, где <tex>k</tex> {{---}} количество точек в ответе.
Тут все сложнее. Представим, что мы ищем <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_*_log_%5E(\log^2\,n+answerd_-_1)</tex> с помощью двухмерного [[Дерево_интервалов__n_(interval_treerange_tree)_и_пересечение_точки_с_множеством_интервалов| range tree]]. А может можно Просто для каждого прямоугольника добавим в range tree его левый верхний угол. Задав запрос в виде нашего прямоугольника, мы получим то, что и прощенужно.
Утверждается, что все прямоугольники, которые нам нужны {{---}} объединение ответов, полученных тремя способами. Оценивать асимтотику всего этого мне совсем не хочется, но, наверное, это <tex>O(\log^2\,n+answer)</tex> времени на запрос. <tex>O(n\log\,n)</tex> памяти из-за range tree и <tex>O(n\log^2\,n)</tex> на построение. Но, возможно, я что-то забыл или что-то можно сделать более эффективно.
