Итак, многие из Вас знают, что можно легко и просто хешировать множества. Например, множество $$$s = { s_1, s_2, ..., s_n }$$$ можно захешировать числом $$$x(s_1) + x(s_2) + ... + x(s_n)$$$ или даже $$$x(s_1) \oplus ... \oplus x(s_n)$$$ (где $$$x$$$ — какая-то случайная функция). С такими хешом можно поддерживать операции добавления и удаления элемента, слияния множеств, нахождения симметричной разности множеств и так далее. Но у такого подхода есть и достаточно серьезный минус, например, имея на руках только хеш мы не можем понять, какие элементы содержит это множество.
Сегодня я хочу поведать о не очень сложной структуре данных, основанной на дереве отрезков, которая позволяет совершать различные операции с множествами, в частности, сравнивать эти множества за время O(1), надеюсь, после прочтения вы поделитесь своими идеями, как ее можно улучшить и какие еще операции с ней можно делать. :D
Итак, для начала рассмотрим следующую задачу. В первой строке даны числа $$$N,Q \leq 10^5$$$, отвечая на запросы нам требуется поддерживать $$$N$$$ множеств, пронумерованные числами от 1 до $$$N$$$. В последующих $$$Q$$$ строках указаны запросы, каждый из которых может иметь следующий вид:
$$$1$$$ $$$i$$$ $$$x$$$ — добавить в $$$i$$$-ое множество элемент $$$1 \leq x \leq N$$$, если $$$x$$$ уже содержится в этом множестве, то ничего делать не надо
$$$2$$$ $$$i$$$ $$$x$$$ — удалить элемент $$$1 \leq x \leq N$$$ из $$$i$$$-ого множества, аналогично, если элемента в множестве нет, то множество не изменяется
$$$3$$$ $$$i$$$ $$$j$$$ — скопировать множество $$$j$$$ в множество с номером $$$i$$$.
Да, эту задачу можно решать теми же хешами и персистентными декартовыми деревьями, но это слишком сложно. На самом деле задача намного проще чем это кажется на первый взгляд. Давайте заведем дерево отрезков на $$$N$$$ элементов, где каждой вершине будет присвоен некоторый класс $$$h$$$, который будет обладать следующими несложными свойствами:
$$$h_v = 0$$$ тогда и только тогда, когда нет ни одного числа, за которое ответственно поддерево вершины $$$v$$$.
$$$h_v = 1$$$ тогда и только тогда, когда $$$v$$$ — лист, и число, соответствующее этой вершине содержится в множестве.
в ином случае $$$h_v$$$ однозначно определяется классами левого и правого ребенка вершины $$$v$$$ и наоборот.
Понятно, что заранее мы никак не можем определить классы на все случаи жизни, так что давайте постепенно будем их добавлять по мере надобности, для этого заведем функцию vertex(i, j), которая по классам i и j будет определять класс вершины, являющейся родителем этих вершин:
Дело остается за малым, давайте напишем стандартное дерево отрезков и будет нам счастье! Но, к сожалению все не так просто, если мы будем честно поддерживать дерево отрезков то на поддержку $$$N$$$ деревьев нам понадобится $$$O(N^2)$$$ памяти, вместо этого давайте просто поддерживать класс, к которому относится корень нашего дерева отрезков, но уже, кстати, неявного, ведь по классу вершины можно однозначно восстановить классы ее сыновей. Запросы добавления и удаления ограничиваются спуском по дереву и аккуратным пересчетом классов вершин, код, поясняющий данную идею:
Данные функции возвращают класс полученного множества целиком, для того, чтобы сравнить два множества требуется просто сравнить их классы, которые по совместительству и являются идентификаторами наших множеств. Кстати, это весь код решения, исключая ввод и вывод данных. Функции del и add работают за $$$O({\log}^2 n)$$$ или за $$$O(\log n)$$$ если в функции vertex использовать unordered_map, так же возможны константные оптимизации.
Теперь предоставлю упражнения читателям, то есть те вещи, которые умеет делать эта структура, но на которых мне не хочется подробно останавливаться:
Найти минимальный элемент принадлежащий ровно одному множеству из двух множеств $$$a$$$ и $$$b$$$ (просто спуск по дереву отрезков).
Объединение двух множеств (при условии, что нет операции клонирования).
Удаление всех элементов множества, меньших чем $$$x$$$, а так же больших чем $$$x$$$.
Всевозможные суммы, lower_bound и почти все, что умеет обычное ДО.
К тому же, если элементы, хранимые в множестве это, например, не числа, или слишком большие числа, то использование дерева отрезков может быть невозможно, для таких целей можно аналогичным образом хешировать и декартовы деревья. Но тогда по значению ключей, хранящихся в декартовом дереве должна однозначно восстанавливаться структура дерева, добиться этого можно, если значением приоритета вершина будет какая-то функция, зависящая от ключа в вершине (можно, например, просто сохранять приоритет для ключей в unordered_map, хотя, как кажется это немного неадекватно). При совпадении ключа надо считать, что приоритет выше у той вершины, у которой больше соответствующий ключ. Тогда все операции будут выполнимы за $$$O(\log n)$$$ с использованием $$$O(n \log n)$$$ памяти.
Данное рассуждение можно распространить и для хеширования персистентных стеков (обычные стеки всегда можно заменить на персистентные без особых потерь). Тогда хеш пустого стека примем равным $$$0$$$, а хеш стека $$$S$$$ будет взаимнооднозначно определяться хешем стека $$$S$$$ без верхнего элемента и верхним элементом стека $$$S$$$. Условно говоря, это другой взгляд на хранение персистентного стека с помощью дерева.
Теперь перейдем к задачам, которые можно решить с помощью этой структуры данных или описанных выше идей.
(Задача 1). Пусть дано подвешенное дерево на $$$N \leq 10^5$$$ вершинах, где в каждой в каждой вершине $$$v$$$ написано какое-то натуральное число $$$A_v \in { 1, 2, ... , N }$$$. Рассмотрим все вертикальные пути (простой путь у которого один конец это предок другого конца) длины $$$K$$$, для каждого пути посчитаем множество чисел, записанных на вершинах этого пути. Требуется вывести количество различных множеств, которые мы можем определить.
(Задача 2). Есть страна, состоящая из $$$N \leq 10^5$$$ городов, далее с ней по очереди происходят $$$Q$$$ действий, каждое из которых относится к одному из следующих типов:
- Добавляется ребро $$$(u, v)$$$.
- В город $$$v$$$ приезжает ученый, который занимается наукой с порядковым номером $$$1 \leq x \leq 10^6$$$.
- Запрос вида $$$(u, v, R)$$$, на который требуется ответить минимальным натуральным числом $$$L$$$ таким, что, область науки $$$L \leq x \leq R$$$ развита в компоненте связности вершины $$$u$$$ тогда и только тогда, когда он развита в компоненте $$$v$$$. Область науки развита в компоненте связности тогда и только тогда, когда хотя бы в одном городе из этой компоненты есть ученый, занятый этой областью.
- По приказу государства этой страны все ученые из компоненты вершины $$$v$$$, занимающиеся науками из отрезка $$$[L,R]$$$ переезжают в компоненту $$$u$$$.
(Задача 3). Есть подвешенное дерево, на каждом ребре которого записана какая-нибудь латинская буква. Скажем, что корню соответствует пустая строка $$$s(v_0) = \epsilon$$$, а вершине $$$v$$$, из которой ведет ребро с символом $$$w$$$ в ее предка $$$p$$$, сопоставим строку $$$s(v) = w \cdot s(p)$$$. Требуется для любой пары вершин $$$(u,v)$$$ уметь лексикографически сравнивать строки $$$s(u)$$$ и $$$s(v)$$$ за время $$$O(\log N)$$$ и c предпосчетом за $$$O(N \log^2 N)$$$ без использования рандомизированных алгоритмов.
(Задача 4). Даны $$$N$$$ чисел $$$a_1, a_2, \ldots, a_N$$$ в двоичной системе счисления суммарной длиной $$$M$$$. Требуется уметь сравнивать на больше/меньше $$$(a_i \mod 2^x)$$$ с $$$(a_j \mod 2^y)$$$ за время $$$O(1)$$$ и с предпосчетом за время $$$O(M \log N)$$$.
По-хорошему, все эти идеи описывают несколько извращенную персистентность и хеширование деревьев. При достаточной степени развязности сексуальных предпочтений можно так же понять, какой смысл имеет такое хеширование при рассмотрении ориентированных графов, как таким образом можно научиться "хешировать" деки и, например, что метод построения суффиксного массива за $$$O(N \log N)$$$ тесно связан с этой идеей.
