Две оценки
Через сервер идёт поток номеров — слов, запросов, адресов. Хранить счётчик на каждый номер дорого, поэтому их считают наброском Count-Min: d строк по w счётчиков. В строке i номер x попадает в клетку ((ai·x + bi) mod P) mod w, где P = 231 − 1. Оценка числа появлений x — минимум по строкам из клеток x.
Инженер хочет сравнить два способа обновлять набросок на одном и том же потоке. Обычный: при появлении x прибавить 1 к его клетке в каждой строке. Осторожный: сначала найти текущую оценку x, m, и поднять каждую клетку x, которая меньше m + 1, до m + 1; клетки, которые уже больше, не трогать. Для каждого запроса выведите обе оценки.
В третьем тесте поток — 200 000 слов «Войны и мира», каждое заменено номером по частоте: «и» — 1, «в» — 2 и так далее.
Вход
В первой строке d, w и длина потока n (1 ≤ d ≤ 8, 1 ≤ w ≤ 104, 1 ≤ n ≤ 2·105). Во второй — a1, …, ad, в третьей — b1, …, bd (0 ≤ ai, bi < P). В четвёртой — поток: n номеров от 1 до 109. Дальше число запросов q (1 ≤ q ≤ 2000) и q номеров по одному в строке.
Выход
На каждый запрос — две оценки через пробел: обычного наброска и осторожного.
Примеры
Пример 1
2 4 8 967164356 29153372 164071949 1045161374 1 2 1 3 1 4 5 2 4 1 2 3 6
5 5 5 5 2 2 1 1
Пример 2
3 8 12 449815270 997595895 1392220162 928730935 208356165 507535111 7 7 7 1 2 3 4 5 6 8 9 7 4 7 1 9 10
5 4 1 1 1 1 0 0
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Обычный набросок — прямое повторение условия. В осторожном важен порядок: сначала оценка по старым значениям клеток, потом подъём.
2Идея
Держим две таблицы d × w. На каждый номер считаем его d клеток (их удобно запомнить для повторов). В обычной таблице прибавляем 1 во все. В осторожной находим минимум m по клеткам номера и поднимаем каждую до max(клетка, m + 1). На запрос — минимум по клеткам в каждой таблице.
3Разбор
Почему осторожное обновление не ломает гарантию «не меньше правды». Пусть до появления x каждая его клетка не меньше настоящего числа его появлений c. Тогда и минимум m ≥ c, а после подъёма каждая клетка ≥ m + 1 ≥ c + 1 — правда снова под всеми клетками. Чужие номера клетки только поднимают. Значит, осторожная оценка — по-прежнему верхняя граница, а по построению она не больше обычной: обычный набросок поднимает каждую клетку на 1 всегда, осторожный — не больше чем на 1 и только при необходимости.
На «Войне и мире» с 512 клетками в строке разница видна сразу: для «и» обычная оценка 9849, осторожная 9736. Для редких слов выигрыш больше в процентах: им достаётся меньше шума от частых соседей. Осторожное обновление придумали Кристиан Эстан и Джордж Варгезе для подсчёта сетевого трафика. У него есть цена: его нельзя применить к отрицательным прибавкам, и два наброска нельзя сложить поклеточно — результат зависит от порядка потока.
3+Решение
4Сложность
O(d) на элемент потока и на запрос, O(d·w) памяти.
5Типичные ошибки
- Поднять только одну, наименьшую клетку. Остальные строки отстанут, минимум окажется ниже правды, и набросок перестанет быть верхней границей: первый пример.
- Обновлять клетки по одной, пересчитывая минимум. После подъёма первой клетки минимум меняется; поднимать нужно до m + 1, где m посчитан до обновления.
- Переполнение. ai·x достигает 231·109 — в 64 бита помещается, в 32 — нет.