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

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

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

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

У этой задачи существует решение с помощью алгоритма 3Д Мо, например описанное тут