Формальная постановка: дан массив $$$a$$$ из $$$n$$$ натуральных чисел. Также даны $$$q$$$ запросов двух типов:
посчитать количество различных чисел на отрезке $$$[l, r]$$$;
выполнить присвоение $$$a_p := x$$$.
Запросы даны offline (т.е. все сразу).
У этой задачи существует менее оптимальное решение с помощью алгоритма 3Д Мо, например, описанное тут. Опишем решение, работающее за $$$(n+q)*\sqrt{n+q}$$$.
Т.к. запросы даны заранее, то мы сможем сжать числа и считать, что в любой момент времени $$$a_i \le n+q$$$. Разобьем $$$q$$$ запросов на $$$b$$$ блоков по $$$m$$$ запросов $$$(m*b=q)$$$.
Будем обрабатывать запросы блоками. После завершения обработки всех запросов очередного блока выполним все операции присвоения и "забудем" про них.
Предположим, запросов изменения не было бы. Тогда рассмотрим такой алгоритм решения задачи: будем проходить по массиву слева направо, поддерживая индексы последних вхождений каждого числа. Когда мы перебрали элемент с индексом $$$i$$$, мы можем ответить на все запросы, у которых $$$r=i$$$. Для этого нужно всего лишь посчитать количество индексов последних вхождений, которые больше либо равны $$$l$$$ (для этого можно, например, поддерживать дерево отрезков и обновлять его при изменении множества последних вхождений.) Так решают эту задачу online без запросов изменений с помощью персистентных структур.
Чтобы обрабатывать запросы изменения, изменим этот алгоритм.
Будем поддерживать для каждого числа не только последнее вхождение, а стек индексов его вхождений(в массиве без изменений). Множество последних вхождений будем поддерживать в структуре, которая позволит делать изменение элемента за $$$O(1)$$$ и получать сумму чисел на отрезке за $$$O(\sqrt{n})$$$. Во всех позициях, которые являются последними вхождениями какого-то числа будем ставить $$$1$$$, а в остальных $$$0$$$. Тогда очевидно, как обрабатывать изменения множества последних вхождений.
Для ответа на очередной запрос будет необходимо учесть изменения массива, которые произошли до этого запроса. Каждый запрос изменения характеризуется тройкой чисел $$$i, p, x$$$, где $$$i$$$ номер запроса, а $$$p$$$ и $$$x$$$ — числа, описывающие запрос.
Для ответа на запрос первого типа(посчитать количество различных чисел на отрезке) $$$j, l, r$$$ ($$$j$$$ — номер запроса) переберем все запросы изменения, у которых $$$i < j$$$ в порядке уменьшения $$$p$$$. Если до запроса $$$j$$$, элемент $$$p$$$ изменялся несколько раз, оставим только последнее изменение.
При обработке очередного запроса изменения $$$i, p, x$$$ рассмотрим несколько случаев.
Изменения стека для числа $$$a_p$$$:
$$$p$$$ последний элемент стека вхождений для числа $$$a_p$$$. В таком случае требуется убрать его из стека и обработать изменение множества индексов последних вхождений.
$$$p$$$ не последний элемент стека вхождений для числа $$$a_p$$$. В таком случае ничего менять не надо т.к. последнее вхождение $$$a_p$$$ уже не изменится(из-за того, что мы перебираем запросы изменения в порядке уменьшения $$$p$$$).
Для числа $$$x$$$:
$$$p$$$ больше последнего числа в стеке для числа $$$x$$$. В таком случае требуется добавить его в стек и обработать изменения в множестве последних элементов.
$$$p$$$ меньше последнего числа в стеке для числа $$$x$$$. В таком случае ничего менять не надо т.к. последнее вхождение $$$x$$$ уже не изменится(из-за того, что мы перебираем запросы изменения в порядке уменьшения $$$p$$$).
После обработки всех запросов изменения получим сумму чисел в структуре на отрезке $$$[l, r]$$$, а потом откатим все изменения(для этого нужно дополнительно хранить какие изменения в стеках мы делали).
Для удобства и эффективного перебора запросов изменения отсортируем все запросы изменения в начале обработки блока запросов в таком порядке: в первую очередь по уменьшению $$$p$$$, при равных $$$p$$$ по уменьшению $$$i$$$.
Также заметим, что при обработке запросов изменения можно не изменять структуру данных для множества последних вхождений, а просто корректировать сумму чисел на отрезке [l, r], которую следует посчитать перед обработкой запросов изменения.
Итого мы обработали $$$b$$$ блоков, в каждом блоке мы проходили весь массив, поддерживали стек индексов вхождений для каждого элемента и структуру данных с суммой чисел за $$$O(n+q)$$$ т.к. изменения в структуре делаются за $$$O(1)$$$. Также для каждого запроса подсчета количества различных элементов (их $$$O(q)$$$) мы обрабаотывали $$$O(m)$$$ запросов изменения и обращались к структуре данных за $$$O(\sqrt{n})$$$. Если сделать $$$m$$$ и $$$b$$$ примерно равными $$$\sqrt{q}$$$, то получим нужную асимтотику.
Comments (0)
