Массовые операции на версиях персистентного дерева отрезков.

Правка ru1, от bobr_salavat, 2024-02-13 17:10:42

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

Теги структуры данных, запросы на отрезках, дерево отрезков, персистентность

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru25 Русский bobr_salavat 2024-02-21 14:35:46 15 Мелкая правка: 'времени и памяти.\n' -> 'времени и $O((N+Q)logN)$ памяти.\n'
ru24 Русский bobr_salavat 2024-02-21 11:24:49 6
ru23 Русский bobr_salavat 2024-02-21 11:24:09 0 (опубликовано)
ru22 Русский bobr_salavat 2024-02-21 11:22:15 6 Мелкая правка: 'амяти.\n\nЗадачу л' -> 'амяти.\n\nP.S.\nЗадачу л'
ru21 Русский bobr_salavat 2024-02-21 11:21:39 2
ru20 Русский bobr_salavat 2024-02-21 11:21:01 28
ru19 Русский bobr_salavat 2024-02-21 11:18:50 49
ru18 Русский bobr_salavat 2024-02-21 10:20:14 5
ru17 Русский bobr_salavat 2024-02-21 10:19:42 28 Мелкая правка: 'X$ из $MP_A_X$, и встав' -> 'X$ из $MP_(A_X)$, и встав'
ru16 Русский bobr_salavat 2024-02-21 10:18:11 2 Мелкая правка: 'X$ из $MP_A_X$, и встав' -> 'X$ из $MP_(A_X)$, и встав'
ru15 Русский bobr_salavat 2024-02-21 10:17:43 3284 Мелкая правка: 'X = X2. \n$\nТеперь о' -> 'X = X2. \n\nТеперь о'
ru14 Русский bobr_salavat 2024-02-21 10:15:16 2 Мелкая правка: 'X = X2. \n$\nТеперь о' -> 'X = X2. \n\nТеперь о'
ru13 Русский bobr_salavat 2024-02-21 10:15:01 4
ru12 Русский bobr_salavat 2024-02-21 10:14:46 52
ru11 Русский bobr_salavat 2024-02-21 09:05:29 2 Мелкая правка: 'ан массив А, из N цел' -> 'ан массив $А$, из N цел'
ru10 Русский bobr_salavat 2024-02-21 09:05:19 6 Мелкая правка: 'ан массив А, из N цел' -> 'ан массив $А$, из N цел'
ru9 Русский bobr_salavat 2024-02-21 09:05:00 2 Мелкая правка: 'ан массив А, из N цел' -> 'ан массив $А$, из N цел'
ru8 Русский bobr_salavat 2024-02-21 09:03:51 778
ru7 Русский bobr_salavat 2024-02-13 20:12:26 160
ru6 Русский bobr_salavat 2024-02-13 20:06:40 378
ru5 Русский bobr_salavat 2024-02-13 19:59:35 681
ru4 Русский bobr_salavat 2024-02-13 17:35:16 650
ru3 Русский bobr_salavat 2024-02-13 17:20:11 10
ru2 Русский bobr_salavat 2024-02-13 17:19:49 433
ru1 Русский bobr_salavat 2024-02-13 17:10:42 685 Первая редакция (сохранено в черновиках)