Обзор решений задачи KQUERY

За последнее время у меня набралось определённое количество заметок на различные темы, с которыми до конца не ясно что делать. Скорее всего, для синих эта информация не слишком актуальна, для красных — давно очевидна. Из этих заметок вряд ли получится сделать статьи, а достаточно заинтересованный человек вполне может собрать всю приведённую в них информацию из интернета по частям самостоятельно. Тем не менее, я всё же решил сделать пост (или, может быть несколько) на Codeforces, в надежде, что эти сведения для кого-нибудь окажутся полезными.

Оригинальная задача KQUERY формулируется следующим образом. Дан массив $\text{[math]}$ размера $\text{[math]}$ , а также $\text{[math]}$ запросов вида $\text{[math]}$ — определить количество элементов, больших $\text{[math]}$ , на отрезке $\text{[math]}$ .

Сразу следует заметить, что из-за достаточно малого TL вердикт Accepted по оригинальной задаче получает только одно из приведённых ниже решений. Тем не менее, рассмотрение альтернативных подходов к задаче также не лишено смысла.

Online-версия задачи KQUERY — KQUERYO. Среди её особенностей — увеличенный TL и некорректные тесты (см. комментарии к задаче). Все показанные online-решения получают применительно к данной задаче вердикт Accepted.

Dynamic-версия задачи KQUERY — KQUERY2. В данном посте эта задача (пока) не рассматривается; её обсуждение можно найти здесь.

Решение #1: merge tree

Препроцессинг $\text{[math]}$ , ответ на запрос $\text{[math]}$ , online

Код решения

Создадим дерево отрезков, у которого в вершине, соответствующей подотрезку $\text{[math]}$ , хранится отсортированный вектор элементов массива $\text{[math]}$ (в иностранных источниках такое дерево отрезков иногда называют merge tree). Объединять отсортированные вектора можно при помощи алгоритма STL merge().

При обработке запроса к отрезку $\text{[math]}$ мы, как обычно, спускаемся к вершинам, подотрезки которых входят в целевой отрезок, и в каждой из этих вершин выполняем двоичный поиск, чтобы определить количество элементов, больших $\text{[math]}$ .

Видео об этом решении

Решение #1a: частичное каскадирование

Препроцессинг $\text{[math]}$ , ответ на запрос $\text{[math]}$ , online

Код решения

В предыдущем решении мы использовали двоичный поиск, чтобы в каждой вершине, подотрезок которой входит в отрезок запроса, находить индекс первого элемента, большего $\text{[math]}$ . Мы могли бы определять этот индекс за $\text{[math]}$ , если бы в каждой вершине была сохранена дополнительная информация.

Пусть $\text{[math]}$ — отсортированный вектор, хранящийся в вершине $\text{[math]}$ , $\text{[math]}$ и $\text{[math]}$ — отсортированные вектора, хранящиеся в её левом и правом потомках. Пусть в вершине $\text{[math]}$ также имеются массивы $\text{[math]}$ и $\text{[math]}$ , такие что $\text{[math]}$ — индекс первого элемента, большего или равного $\text{[math]}$ , в массиве $\text{[math]}$ , $\text{[math]}$ — аналогичный индекс в массиве $\text{[math]}$ . Тогда, зная индекс $\text{[math]}$ первого элемента, большего $\text{[math]}$ , в массиве вершины $\text{[math]}$ , мы за $\text{[math]}$ определяем индекс первого элемента, большего $\text{[math]}$ , в массивах вершин-потомков (это $\text{[math]}$ и $\text{[math]}$ ).

Массивы $\text{[math]}$ и $\text{[math]}$ формируются в функции build(), когда выполняется объединение двух отсортированных массивов в один. Можно выполнять это объединение вручную, как в сортировке слиянием, попутно заполняя массивы $\text{[math]}$ и $\text{[math]}$ .

При обработке запроса достаточно выполнить бинпоиск в корневой вершине, чтобы найти индекс первого элемента, большего $\text{[math]}$ , а далее обновлять его значениями из $\text{[math]}$ и $\text{[math]}$ . Данную технику называют частичным каскадированием (fractional cascading), она позволяет снять лишний логарифм при обработке запросов.

Практика, однако, показывает, что несмотря на лучшую асимптотическую оценку, данное решение работает на 30-40% медленнее предыдущего, поэтому пользоваться им не стоит.

Решение #2: сканирующая прямая по значениям (ординатам)

Препроцессинг $\text{[math]}$ , ответ на запрос $\text{[math]}$ , offline

Код решения

Рассмотрим геометрическую интерпретацию исходной задачи. Если элементы массива $\text{[math]}$ представить на плоскости в виде точек $\text{[math]}$ , то ответом на запрос $\text{[math]}$ является количество точек, лежащих выше отрезка $\text{[math]}$

Введём два вида событий: появление точки и появление запроса. Отсортируем все события в порядке убывания ординат (для точек это $\text{[math]}$ , для запросов — $\text{[math]}$ ). По абсциссам построим стандартное дерево отрезков для суммы, в котором будем отмечать появление точек.

При обработке появления точки присваиваем в дереве отрезков единицу её абсциссе $\text{[math]}$ . При обработке появления запроса определяем сумму на отрезке $\text{[math]}$ . Заметим, что если разные события имеют одинаковую ординату, в первую очередь должны обрабатываться события, связанные с запросами.

Решение #3: сканирующая прямая по индексам (абсциссам)

Препроцессинг $\text{[math]}$ , ответ на запрос $\text{[math]}$ , offline

Код решения

Продолжим использовать ту же геометрическую интерпретацию задачи, что и для предыдущего решения, но теперь сканирующая прямая движется не сверху вниз, а слева направо.

Введём три вида событий: появление точки, начало запроса, конец запроса. Отсортируем все события в порядке возрастания абсцисс (для точек это $\text{[math]}$ , для начал запросов — $\text{[math]}$ , для концов запросов — $\text{[math]}$ ). По ординатам построим стандартное дерево отрезков для суммы, в котором будем отмечать появление точек.

При обработке появления точки присваиваем в дереве отрезков единицу её ординате $\text{[math]}$ . При обработке начала запроса вычитаем из ответа сумму на отрезке $\text{[math]}$ , при обработке конца запроса добавляем к ответу сумму на отрезке $\text{[math]}$ . Если разные события имеют одинаковую абсциссу, сначала обрабатываются начала запросов, затем точки, затем концы запросов.

Решение #3a: неявное дерево отрезков

Препроцессинг $\text{[math]}$ , ответ на запрос $\text{[math]}$ , offline

Код решения

Используем сжатие координат или неявное дерево отрезков, чтобы снизить потребление памяти с $\text{[math]}$ до $\text{[math]}$ . Время обработки запроса при этом сократится от $\text{[math]}$ до $\text{[math]}$ .

Неявное дерево отрезков строится не в массиве, а полностью на указателях. Новые вершины создаются только в том случае, если к ним обращается функция модификации дерева.

Решение #3b: персистентное дерево отрезков

Препроцессинг $\text{[math]}$ , ответ на запрос $\text{[math]}$ , online

Код решения

Оставим в геометрической интерпретации только точки и сохраним версии неявного дерева отрезков для каждого индекса $\text{[math]}$ . Каждая новая версия не дублирует все вершины предыдущей, а добавляет только $\text{[math]}$ изменённых вершин.

Для ответа на запрос $\text{[math]}$ требуется вычислить сумму на отрезке $\text{[math]}$ в версии $\text{[math]}$ и вычесть сумму на отрезке $\text{[math]}$ в версии $\text{[math]}$ .

Решение #4: sqrt-декомпозиция

Препроцессинг $\text{[math]}$ , ответ на запрос $\text{[math]}$ , online

Код решения

Разделим исходный массив на блоки размером $\text{[math]}$ (получится $\text{[math]}$ блоков). Отсортируем каждый из блоков.

Пусть выполняется запрос к отрезку $\text{[math]}$ . В тех блоках, которые полностью покрываются отрезком запроса, количество чисел, больших $\text{[math]}$ , может быть найдено двоичным поиском. На концах отрезка $\text{[math]}$ , не покрывающих полностью соответствующие блоки (а также в том случае, когда $\text{[math]}$ и $\text{[math]}$ принадлежат одному блоку), ответ считается наивным методом за линейное время. Таким образом, время ответа на запрос выражается как $\text{[math]}$ .

При $\text{[math]}$ получаем классическую sqrt-декомпозицию, имеющую время обработки запроса $\text{[math]}$ . Можно попытаться улучшить это значение, подобрав размер $\text{[math]}$ так, чтобы минимизировать выражение $\text{[math]}$ . При $\text{[math]}$ таким значением будет $\text{[math]}$ . Тем не менее, фактическое увеличение производительности по сравнению с sqrt-декомпозицией составляет ~5%, что влечёт общую нецелесообразность подобной оптимизации.

Сравнение быстродействия решений

Сформируем массив $\text{[math]}$ размера $\text{[math]}$ , заполненный случайными числами из диапазона $\text{[math]}$ . Затем выполним $\text{[math]}$ случайных KQUERY-запросов к данному массиву. Для каждого значения $\text{[math]}$ произведём 10 тестов, в качестве итогового времени возьмём среднее.

Можно видеть, что наиболее быстрым из online-решений является использование дерева отрезков с отсортированными подмассивами в вершинах, имеющее асимптотику $\text{[math]}$ на запрос (!).

Как было упомянуто ранее, в оригинальной задаче KQUERY вердикт Accepted получает только offline-решение #2 (сканирующая прямая по убыванию ординат). Можно попробовать произвести (неасимптотические) оптимизации других решений: не использовать ООП-стиль, заменить std::vector на статические массивы и т. д. Описание оптимизаций, достойных внимания, приветствуется в комментариях.

Другие задачи, сводящиеся к KQUERY

Количество различных чисел на отрезке (DQUERY)

Существует простое сведение задачи DQUERY к задаче KQUERY за время $\text{[math]}$ .

Определим массив $\text{[math]}$ , такой что $\text{[math]}$ . Другими словами, $\text{[math]}$ -й элемент массива $\text{[math]}$ содержит индекс следующего справа элемента, равного $\text{[math]}$ (если $\text{[math]}$ — последнее появление элемента, то $\text{[math]}$ ).

Количество различных элементов на отрезке — это количество элементов, справа от которых на отрезке нет равных им, то есть количество таких $\text{[math]}$ , что $\text{[math]}$ . Таким образом, результат запроса DQUERY $\text{[math]}$ к массиву $\text{[math]}$ равен результату запроса KQUERY $\text{[math]}$ к массиву $\text{[math]}$ .

На spoj.com задачу DQUERY можно сдать с использованием любого из показанных выше решений, кроме самого медленного (#4, sqrt-декомпозиция).

Обсуждение задачи на Codeforces

K-я порядковая статистика на отрезке (MKTHNUM)

Используя бинарный поиск по ответу, любое online-решение задачи KQUERY можно преобразовать в решение задачи MKTHNUM, асимптотика которого будет в $\text{[math]}$ раз выше: из решений KQUERY с асимптотикой $\text{[math]}$ и $\text{[math]}$ получаются решения MKTHNUM с асимптотикой $\text{[math]}$ $\text{[math]}$ соответственно.

На spoj.com задачу MKTHNUM можно сдать с использованием любого из online-решений, кроме самого медленного (#4, sqrt-декомпозиция). В решении #3b нужно аккуратно учитывать отрицательные элементы массива.

Важно, что эта задача имеет online-решение с временем обработки запроса $\text{[math]}$ . Это решение (не рассматриваемое здесь подробно) получается из решения #3b, но вместо бинарного поиска по ответу используется параллельный спуск по деревьям отрезков версий $\text{[math]}$ и $\text{[math]}$ .

Обсуждение задачи на Codeforces

Решения указанных задач также приведены в лекции ЗКШ 2015 (автор Burunduk1).