Формальная постановка: дан массив $$$a$$$ из $$$n$$$ натуральных чисел. Также даны $$$q$$$ запросов двух типов:
посчитать количество различных чисел на отрезке $$$[l, r]$$$;
выполнить присвоение $$$a_p := x$$$.
Запросы даны offline (т.е. все сразу).
У этой задачи существует менее оптимально решение с помощью алгоритма 3Д Мо, например описанное тут. Опишем решение, работающее за $$$(n+q)*\sqrt{q}+q*\sqrt{n+q}$$$.
Т.к. запросы даны заранее, то мы сможем сжать числа и считать, что в любой момент времени $$$a_i \le n+q$$$. Разобьем $$$q$$$ запросов на $$$b$$$ блоков по $$$m$$$ запросов $$$(m*b=q)$$$.
Будем обрабатывать запросы блоками. После завершения обработки всех запросов очередного блока выполним все операции присвоения и "забудем" про них.
Предположим, запросов изменения не было бы. Тогда рассмотрим такой алгоритм решения задачи: будем проходить по массиву слева направо, поддерживая индексы последних вхождений каждого числа. Когда мы перебрали элемент с индексом $$$i$$$, мы можем ответить на все запросы, у которых $$$r=i$$$. Для этого нужно всего лишь посчитать количество индексов последних вхождений, которые больше либо равны $$$l$$$ (для этого можно, например, поддерживать дерево отрезков и обновлять его при изменении множества последних вхождений.)
Чтобы обрабатывать запросы изменения, изменим этот алгоритм.
Во-первых будем поддерживать для каждого числа не только последнее вхождение, а стек индексов его вхождений.
