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

Правка ru10, от dushenkov, 2024-04-03 00:04:01
Предыстория

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

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

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

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

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

История

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