Предисловие:
Я не утверждаю, что мое решение самое лучшее/простое/оптимальное и на самом деле что оно вообще работает, просто придумал и решил написать сюда. Если у вас есть другое решение, можете предложить его в комментариях. Буду считать что вам знакомы следующие темы: неявное дерево отрезков, массовые операции на дереве отрезков, персистентное дерево отрезков.
Задача:
Дан массив $$$A$$$, из $$$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$$$. Теперь изменение значения $$$V$$$ = $$$A_X$$$, равносильно удалению $$$MP_V$$$ из $$$MP_D$$$, и вставить $$$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)$$$ вершин. При изменении вершины будем записывать в некоторый массив, созданный для каждой вершины нулевой версии, размера равного количеству версий конкретной вершины и при запросе получения значения в вершине, просто брать сумму на префиксе до соответствующей версии. Так, нужно хранить все версии в структуре, поддерживающей следующие операции: добавление элемента в конец, получение суммы на префиксе, изменение в точке. Нам подходит дерево фенвика, каждую операцию выполняет за $$$O(log N)$$$, и не ухудшает память. По итогу, все операции мы сделаем за $$$O((N + Q) log^2 N)$$$ времени и $$$O((N+Q)logN)$$$ памяти.
P.S. Задачу лень искать, мб сам сделаю потом.
