Блог пользователя tiom4eg

Автор tiom4eg, 2 года назад, По-русски

Доброго времени суток, Codeforces!

Недавно я решал задачи на структуры данных из архива, и мне пришли в голову идеи нескольких задач. Я хотел бы поделиться ими с вами и узнать ваше мнение о них. Косвенно этот блог вдохновлён похожим блогом от BERNARD. Также я буду очень рад, если в комментариях предложат решения задач (быстрее, чем за $$$O(nq)$$$) или их модификации. Любой фидбек очень важен!

В любом случае, перейдём к задачам.

Задача 1. Имеется множество из $$$n$$$ отрезков на прямой, заданных границами $$$l_i$$$ и $$$r_i$$$ ($$$0$$$ <= $$$l_i$$$ <= $$$r_i$$$ <= $$$10^9$$$). Также имеется $$$q$$$ запросов, каждый задан отрезком с границами $$$x_i$$$ и $$$y_i$$$ ($$$0$$$ <= $$$x_i$$$ <= $$$y_i$$$ <= $$$10^9$$$). Для каждого запроса необходимо найти количество отрезков, вложенных в отрезок запроса.

Задача 2. Аналогично задаче 1, но имеются запросы добавления отрезков в множество.

Задача 3. Аналогично задаче 2, но имеются запросы удаления отрезков из множества (гарантируется, что удаляемый отрезок точно есть в множестве).

Задача 4. Аналогично задаче 2, но после добавления отрезка создаётся новая версия множества и нужно в онлайне отвечать на запросы к определённой версии множества.

Задача 5. Аналогично задаче 1, но в 2D/kD (т.е. множество состоит из прямоугольников на плоскости, нужно находить количество прямоугольников на прямоугольнике).

Задача 6. Аналогично задаче 1, но вместо отрезков будем использовать простые пути в дереве, необходимо находить количество вложенных в путь запроса путей.

Задача 7. Аналогично задачам 1-4, но каждый отрезок имеет свой вес и необходимо находить не количество, а минимум/максимум среди весов вложенных отрезков.

Задача 8. Аналогично задаче 7, но нужно находить количество различных весов вложенных отрезков.

Задача 9. Аналогично задаче 7, но нужно находить медиану/k-ую статистику по весам вложенных отрезков.

Задача 10. Имеется множество из $$$n$$$ отрезков на координатной плоскости, заданных двумя точками, координаты которых не превосходят $$$10^9$$$. Необходимо отвечать на запросы количества отрезков из множества в прямоугольнике.

Задача 11. Аналогично задаче 10, но нужно уметь выполнять те же операции, что и в задачах 1-4 и 7-9.

  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

P1. $$$\mathcal{O}((n+q)\log n)$$$, offline

Solution

P2 (and also P3 actually). $$$\mathcal{O}((n+q)\log^2 n)$$$, offline

Solution
  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    P1-P3 can all be solved online with an ordered set on a segtree. I believe 1, 2, 3, 4, 7, 8, 9 can all be solved using 2d segtree

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Задачи 1-3 решаются с помощью дерева отрезков.

Спойлер
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Или по-человечески хранить фенвик, считав все запросы в оффлайне и пожав координаты в каждой вершине ДО)

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну и задача 5 — это просто написать трехмерное ДО)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Problem 6