Формальная постановка: дан массив $$$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$$$ (для этого можно, например, поддерживать дерево отрезков и обновлять его при изменении множества последних вхождений.) Так решают эту задачу online без запросов изменений с помощью персистентных структур.
Чтобы обрабатывать запросы изменения, изменим этот алгоритм.
Будем поддерживать для каждого числа не только последнее вхождение, а стек индексов его вхождений(в массиве без изменений). Для ответа на очередной запрос будет необходимо учесть изменения массива, которые произошли до этого запроса. Каждый запрос изменения характеризуется тройкой чисел $$$i, p, x$$$, где $$$i$$$ номер запроса, а $$$p$$$ и $$$x$$$ — числа, описывающие запрос.
Для ответа на запрос первого типа(посчитать количество различных чисел на отрезке) $$$j, l, r$$$ ($$$j$$$ — номер запроса) переберем все запросы изменения, у которых $$$i < j$$$ в порядке уменьшения $$$p$$$. Если до запроса $$$j$$$, элемент $$$p$$$ изменялся несколько раз, оставим только последнее изменение.
