81
правка
Изменения
Нет описания правки
req(tree->up, y1, y2, x_max, ans)
</code>
== Причем тут пересечение прямоугольника с множеством прямоугольников? ==
Хотел бы я знать.
Ну а вообще задача решается следующим образом. Будем находить ответ тремя разными способами, а их объединение и будет настоящим ответом. Будем считать, что объединение множеств можно делать за <tex>O(n)</tex>, где <tex>n</tex> {{---}} суммарное количество элементов в них.
'''Первый способ.''' Найдем все прямоугольники, в которых прямоугольник из запроса лежит полностью. Для этого нужно решать такую задачу. Дано множество прямоугольников, для заданной точки найти все прямоугольники, в которых она лежит. Это точно можно решать за <tex>O(\log^2\,n+answer)</tex> с помощью двухмерного [[Дерево_интервалов_(interval_tree)_и_пересечение_точки_с_множеством_интервалов]]. А может можно и проще.
'''Второй способ.''' Найдем все прямоугольники, которые полностью лежат внутри заданного в запросе. Для этого воспользуемся [[Перечисление_точек_в_произвольном_прямоугольнике_за_n_*_log_%5E(d_-_1)_n_(range_tree)]]. Просто для каждого прямоугольника добавим в range tree его левый верхний угол. Задав запрос в виде нашего прямоугольника, мы получим то, что и нужно.
'''Третий способ.''' Найдем все прямоугольники, хотя бы одна сторона которого пересекает заданный в запросе. Для этого воспользуемся [[Пересечение_прямоугольника_с_множеством_непересекающихся_отрезков_(segment_tree)]]. В структуру добавим все стороны всех прямоугольников и зададим запрос в виде нашего прямоугольника.
Утверждается, что все прямоугольники, которые нам нужны {{---}} объединение ответов, полученных тремя способами. Оценивать асимтотику всего этого мне совсем не хочется, но, наверное, это <tex>O(\log^2\,n+answer)</tex> времени на запрос. <tex>O(n\log\,n)</tex> памяти из-за range tree и <tex>O(n\log^2\,n)</tex> на построение. Но, возможно, я что-то забыл или что-то можно сделать более эффективно.
