Предисловие:

Я не утверждаю, что мое решение самое лучшее/простое/оптимальное и на самом деле что оно вообще работает, просто придумал и решил написать сюда. Если у вас есть другое решение, можете предложить его в комментариях. Буду считать что вам знакомы следующие темы: неявное дерево отрезков, массовые операции на дереве отрезков, персистентное дерево отрезков.

Задача:

Дан массив А, из N целых чисел. Дано Q запросов двух типов: (1, L, R) — найти кол-во различных чисел на отрезке, (2, X, D) — заменить число на позиции X числом D. Будем считать что на запросы нельзя отвечать оффлайн.

Решение:

Для начала рассмотрим задачу без обновлений. Будем хранить массив B размера N, где B_i — индекс следующего элемента в массиве A равного A_i. Более формально, B_i = min j: j > i, A_j = A_i. Построим на персистентное неявное дерево отрезков, назовем его T, его версии будут храниться в массиве Vers. Пройдемся по массиву для каждого i: 1 <= i <= n добавим B_i в T и сохраним новую версию в Vers_i.