Количество различных элементов на отрезке + изменение элемента OFFLINE

Revision ru31, by dushenkov, 2024-04-03 13:24:54
Предыстория

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

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

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

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

У этой задачи существует менее оптимально решение с помощью алгоритма 3Д Мо, например описанное тут. Опишем решение, работающее за $$$(n+q)*\sqrt{q}+q*\sqrt{n}$$$.

Т.к. запросы даны заранее, то мы сможем сжать числа и считать, что в любой момент времени $$$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$$$:

  1. $$$p$$$ последний элемент стека вхождений для числа $$$a_p$$$. В таком случае требуется убрать его из стека и обработать изменение множества индексов последних вхождений.

  2. $$$p$$$ не последний элемент стека вхождений для числа $$$a_p$$$. В таком случае ничего менять не надо т.к. последнее вхождение $$$a_p$$$ уже не изменится(из-за того, что мы перебираем запросы изменения в порядке уменьшения $$$p$$$).

Для числа $$$x$$$:

  1. $$$p$$$ больше последнего числа в стеке для числа $$$x$$$. В таком случае требуется добавить его в стек и обработать изменения в множестве последних элементов.

  2. $$$p$$$ меньше последнего числа в стеке для числа $$$x$$$. В таком случае ничего менять не надо т.к. последнее вхождение $$$x$$$ уже не изменится(из-за того, что мы перебираем запросы изменения в порядке уменьшения $$$p$$$).

После обработки всех запросов изменения получим сумму чисел в структуре на отрезке $$$[l, r]$$$, а потом откатим все изменения(для этого нужно дополнительно хранить какие изменения в стеках мы делали).

Также заметим, что при обработке запросов изменения можно не изменять структуру данных для множества последних вхождений, а просто корректировать сумму чисел на отрезке [l, r], которую следует посчитать перед обработкой запросов изменения.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru37 Russian dushenkov 2024-04-03 14:32:26 2 Мелкая правка: '\n\n<spoiler' -> '\n<spoiler' (опубликовано)
ru36 Russian dushenkov 2024-04-03 14:31:02 4826
ru35 Russian dushenkov 2024-04-03 13:46:10 1
ru34 Russian dushenkov 2024-04-03 13:45:36 1
ru33 Russian dushenkov 2024-04-03 13:42:52 216
ru32 Russian dushenkov 2024-04-03 13:38:55 491
ru31 Russian dushenkov 2024-04-03 13:24:54 243
ru30 Russian dushenkov 2024-04-03 13:21:14 201
ru29 Russian dushenkov 2024-04-03 13:16:28 163
ru28 Russian dushenkov 2024-04-03 13:14:28 85
ru27 Russian dushenkov 2024-04-03 13:12:49 340
ru26 Russian dushenkov 2024-04-03 13:07:03 186
ru25 Russian dushenkov 2024-04-03 13:02:02 915
ru24 Russian dushenkov 2024-04-03 12:43:19 45
ru23 Russian dushenkov 2024-04-03 12:42:27 163
ru22 Russian dushenkov 2024-04-03 12:40:08 53
ru21 Russian dushenkov 2024-04-03 12:37:58 122
ru20 Russian dushenkov 2024-04-03 12:35:04 98
ru19 Russian dushenkov 2024-04-03 12:33:04 270
ru18 Russian dushenkov 2024-04-03 12:26:39 51
ru17 Russian dushenkov 2024-04-03 12:25:23 204
ru16 Russian dushenkov 2024-04-03 12:14:32 320
ru15 Russian dushenkov 2024-04-03 12:08:50 191
ru14 Russian dushenkov 2024-04-03 00:14:07 149
ru13 Russian dushenkov 2024-04-03 00:07:19 62
ru12 Russian dushenkov 2024-04-03 00:05:07 97
ru11 Russian dushenkov 2024-04-03 00:04:22 12
ru10 Russian dushenkov 2024-04-03 00:04:01 5
ru9 Russian dushenkov 2024-04-02 23:59:45 176
ru8 Russian dushenkov 2024-04-02 23:47:20 137
ru7 Russian dushenkov 2024-04-02 23:42:30 44
ru6 Russian dushenkov 2024-04-02 23:39:16 4
ru5 Russian dushenkov 2024-04-02 23:28:36 54
ru4 Russian dushenkov 2024-04-02 23:24:15 180
ru3 Russian dushenkov 2024-04-02 23:19:49 27
ru2 Russian dushenkov 2024-04-02 23:16:38 55
ru1 Russian dushenkov 2024-04-02 23:12:04 283 Первая редакция (сохранено в черновиках)