Предисловие:
Я не утверждаю, что мое решение самое лучшее/простое/оптимальное и на самом деле что оно вообще работает, просто придумал и решил написать сюда. Если у вас есть другое решение, можете предложить его в комментариях. Буду считать что вам знакомы следующие темы: неявное дерево отрезков, массовые операции на дереве отрезков, персистентное дерево отрезков.
Задача:
Дан массив А, из N целых чисел. Дано Q запросов двух типов: (1, L, R) — найти кол-во различных чисел на отрезке, (2, X, D) — заменить число на позиции X числом D. Будем считать что на запросы нельзя отвечать оффлайн. 1 <= L_i, R_i, X_i <= N, Q, <= 10 ^ 5, 1 <= A_i, D_i <= 10^9.
Решение:
Для начала рассмотрим задачу без обновлений. Будем хранить массив B размера N, где B_i — индекс следующего элемента в массиве A равного A_i, или N+1 если такого не существует. Более формально, B_i = min j: j > i, A_j = A_i, если такой существует или N+1 иначе. Построим на персистентное неявное дерево отрезков, назовем его T, его версии будут храниться в массиве Vers. Пройдемся по массиву для каждого i: 1 <= i <= n добавим B_i в T и сохраним очередную версию в Vers_i. Теперь можно отвечать на запрос количества различных чисел на отрезке. Найдем для каждого значения присутствующего на отрезке A[L:R], последнее его вхождение в отрезок. Очевидно, что количество таких чисел для всех значений на отрезке — количество различных чисел на отрезке. Найти такое значение очень просто, это лишь количество чисел B_i на отрезке [L:R]: B_i > R. Найти такое количество можно воспользовавшись идеей префиксных сумм. Найти ответ для префикса длины R, и вычесть ответ на префиксе длины L-1. На префиксе произвольной длины K, можно посчитать ответ спуском по Vers_K (нумерация с нуля).
Добавим запрос обновления элемента по индексу (2, X, D). Сначала поймем как меняется массив B. Помимо B, будем хранить в некотором дереве поиска MP (например std::map) пары (Value, Indices), где Value — значение присутствующее в массиве A, Indices — все индексы i: A_i = Value, в отсортированном порядке, при этом в MP будет сортировка только по Value. Теперь изменение значения в массиве A, равносильно удалению X из MP_A_X, и вставить X в MP_D. Рассмотрим операцию удаления из Indices. Пусть X1 — число слева от X в Indices (если оно существует), т.е. максимально меньшее X, X2 — число справа от X (если оно существует, иначе N+1), т.е. минимальное большее X. Тогда массив B изменится так: B_X1 = X2. Рассмотрим операцию добавления числа в Indices. Пусть X1 — число слева от X в Indices (если оно существует), т.е. максимально меньшее X, X2 — число справа от X (если оно существует, иначе N+1), т.е. минимальное большее X. Тогда массив B изменится так: B_X1 = X, B_X = X2.
Теперь осталось научиться делать делать изменения в версиях T. На каждый запрос изменения числа в T нам необходимо изменить O(log N) вершин, следовательно на запрос изменения изменится O(log N) вершин. При изменении вершины будем записывать в некоторый массив delta, созданный для каждой вершины нулевой версии, размера равного количеству версий конкретной вершины и при запросе получения значения в вершине, просто брать сумму на префиксе до соответствующей версии. Так, нужно хранить все версии в структуре, поддерживающей следующие операции: добавление элемента в конец, получение суммы на префиксе, изменение в точке. Нам подходит структура префиксных сумм, каждую операцию выполняет за O(1), и не ухудшает память. По итогу, все операции мы сделаем за O((N + Q) log N) времени и памяти.
Задачу лень искать, мб сам сделаю потом.
