Декодер
Арифметический кодер с адаптивной моделью сжал текст по словам. У модели есть таблица слов в фиксированном порядке и счётчик каждого слова; в начале все счётчики равны единице. Каждое слово занимает отрезок чисел: если сумма счётчиков всех слов, стоящих в таблице раньше него, равна L, а его собственный счётчик c, то отрезок слова — [L, L + c). Для очередного слова кодер передал одно число из его отрезка, а потом увеличил счётчик этого слова на единицу. Декодер повторяет то же самое: находит слово, чей отрезок содержит число, и увеличивает его счётчик.
Напишите декодер. Один из тестов — начало «Войны и мира»: первые 30 000 слов, таблица — их словарь по алфавиту.
Вход
В первой строке m и n (1 ≤ m ≤ 100 000, 1 ≤ n ≤ 50 000) — число слов в таблице и длина текста. Во второй — m разных слов через пробел в порядке таблицы. В третьей — n целых чисел: k-е из них лежит в отрезке k-го слова текста, если считать отрезки по счётчикам после первых k − 1 слов. Все числа меньше суммы счётчиков, то есть меньше m + k − 1.
Выход
Текст — n слов через пробел в одной строке.
Примеры
Пример 1
4 5 в и мир война 3 1 3 1 0
война и мир и в
Пример 2
1 3 ау 0 0 0
ау ау ау
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Пройти по таблице, складывая счётчики, пока сумма не перевалит за число, — это верно, но на таблице из ста тысяч слов каждое слово текста стоит десятки тысяч сложений. Нужны суммы счётчиков, которые быстро обновляются: дерево Фенвика. Но оно отвечает «какая сумма до слова», а спрашивают наоборот.
2Подсказка 2
Суммы префиксов растут вместе с номером, поэтому нужное слово можно найти двоичным поиском — это O(log² m) на слово. А можно ли искать прямо по ячейкам дерева, не вычисляя сумм префиксов заново?
3Идея
Спуск по степеням двойки. Позиция начинается с нуля; пробуем шаги 2k, 2k−1, …, 1. Если позиция кратна 2k+1, то ячейка pos + 2k хранит ровно сумму счётчиков между старой и новой позицией. Если эта сумма не больше остатка числа, все эти слова целиком раньше точки: шагаем и вычитаем сумму. Иначе остаёмся. В конце позиция — число слов, лежащих целиком до точки, то есть номер нужного слова с нуля.
4Разбор
В начале все счётчики — единицы, и строить дерево сложением не нужно: ячейка i отвечает за блок длины lowbit(i) и хранит ровно i & −i. Наибольший шаг — степень двойки, большая m: 1 << m.bit_length(). Шаг, после которого позиция вылезла бы за m, пропускается. После того как слово найдено, его счётчик растёт на единицу обычным путём изменения: прибавлять младшую единицу номера.
Почему ячейка хранит нужный блок: после шагов 2K, …, 2k+1 позиция кратна 2k+1, поэтому у числа pos + 2k младшая единица — ровно 2k, и его блок — счётчики с номерами pos + 1 … pos + 2k.
4+Решение
5Сложность
Спуск — O(log m), изменение — O(log m), всего O(m + n log m). Двоичный поиск по суммам префиксов дал бы O(n log² m) и тоже уложился бы в ограничения, хотя в несколько раз медленнее. Проход по таблице — O(nm): в четвёртом тесте это 50 000 слов по таблице из ста тысяч.
6Типичные ошибки
- Проход по таблице. Верно, но O(m) на слово: даже на начале романа, где в таблице 7848 слов, на Python он не успевает.
- Граница отрезка. Слово с отрезком [L, L + c) содержит L и не содержит L + c; шаг делается при сумме блока не больше остатка. Пятый тест передаёт последнее число каждого отрезка, третий — первое.
- Забыть увеличить счётчик. Декодер обязан менять модель так же, как кодер, иначе со второго слова отрезки разойдутся.
- Начать шаги с наибольшей степени двойки, не большей m. Так тоже верно; важно не начинать с меньшей, иначе до конца таблицы спуск не дойдёт.