Формальная постановка: дан массив $$$a$$$ из $$$n$$$ натуральных чисел. Также даны $$$q$$$ запросов двух типов:

1. посчитать количество различных чисел на отрезке $$$[l, r]$$$;

2. выполнить присвоение $$$a_p := x$$$.

Запросы даны offline (т.е. все сразу).

У этой задачи существует менее оптимально решение с помощью алгоритма 3Д Мо, например описанное тут. Опишем решение, работающее за $$$(n+m)*\sqrt{q}$$$.

Т.к. запросы даны заранее, то мы сможем сжать числа и считать, что в любой момент времени $$$a_i \le n+q$$$. Разобьем $$$q$$$ запросов на $$$b$$$ блоков по $$$m$$$ запросов $$$(m*b=q)$$$.