Предисловие: Я не утверждаю, что мое решение самое лучшее/простое/оптимальное и на самом деле что оно вообще работает, просто придумал и решил написать сюда. Если у вас есть другое решение, можете предложить его в комментариях. Задача: Дан массив А, из N целых чисел. Дано Q запросов двух типов: (1, L, R) — найти кол-во различных чисел на отрезке, (2, X, D) — заменить число на позиции X числом D. Будем считать что на запросы нельзя отвечать оффлайн. Решение: Для начала рассмотрим задачу без обновлений. Можем хранить для каждого a[i] индекс j следующего элемента в массиве равного a[i]. Более формально,