Итак, многие из Вас знают как можно легко и просто хешировать множества, например, множество $$$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), надеюсь, после прочтения вы поделитесь своими идеями, как можно ее улучшить, какие еще операции с ней можно делать, ну и возможно в будущем будете использовать ее в своих задачах.

Итак, для начала рассмотрим следующую задачу. В первой строке даны числа $$$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 будет определять класс вершины, являющейся родителем этих вершин:

int pl[C], pr[C], vc=2;
map<pair<int, int>, int> tab;
int vertex(int i, int j) {
    if (i == 0 && j == 0) return 0;
    int& x = tab[{i, j}];
    if (x == 0) {
        x = vc++;
        pl[x] = i; // классы левого и правого ребенка для любого класса заданы однозначно
        pr[x] = j;
    }
    return x;
}

Клево, тогда дело за малым, давайте напишем стандартное дерево отрезков и будет нам счастье! Но, к сожалению все не так просто, если мы будем честно поддерживать дерево отрезков то на поддержку $$$N$$$ деревьев нам понадобится $$$O(N^2)$$$ памяти, вместо этого давайте просто поддерживать класс, к которому относится корень нашего дерева отрезков, но уже, кстати, неявного, ведь по классу вершины можно однозначно восстановить классы ее сыновей. Запросы добавления и удаления ограничиваются спуском по дереву и аккуратным пересчетом классов вершин, код, поясняющий данную идею:

int add(int v, int l, int r, int x) {
    if (l + 1 == r) {
        return 1;
    } else {
        int m = (l + r) / 2;
        if (x < m) {
            return vertex(add(pl[v], l, m, x), pr[v]);
        } else {
            return vertex(pl[v], add(pr[v], m, r, x));
        }
    }
}
 
int del(int v, int l, int r, int x) {
    if (l + 1 == r) {
        return 0;
    } else {
        int m = (l + r) / 2;
        if (x < m) {
            return vertex(del(pl[v], l, m, x), pr[v]);
        } else {
            return vertex(pl[v], del(pr[v], m, r, x));
        }
    }
}

Данные функции возвращают класс полученного множества целиком, для того, чтобы сравнить два множества требуется просто сравнить их классы, которые по совместительству и являются идентификаторами наших множеств. Кстати, это весь код решения, исключая ввод и вывод данных. Функции 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)$$$ памяти.