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