Не так давно мне попалась задача B с отбора на олимпиаду Высшая проба по информатике, 10 класс:
Дан массив натуральных чисел $$$a$$$ длины $$$n$$$ и $$$q$$$ запросов, $$$j$$$-й из которых содержит натуральное число $$$x_j$$$. Для $$$j$$$-го запроса требуется определить наибольшее число равных элементов в массиве $$$b$$$, полученном из $$$a$$$ следующим образом: $$$b_i=\lfloor\frac{a_i}{x_j}\rfloor$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$.
В оригинальной задаче ограничения следующие: $$$1 \leq n, q, a_i, x_j \leq 3\cdot10^5$$$. В таком случае я увидел следующее решение:
Но изначально условие попало ко мне в искаженном виде. А именно, ограничения были немного изменены: элементы массива и числа в запросах могли достигать стандартной отметки в $$$10^9$$$. Кажется, задача становится менее тривиальной при таких данных. За какое время её можно решать?
Автокомментарий: текст был обновлен пользователем SleepingCat (предыдущая версия, новая версия, сравнить).
Мы умеем решать задачу для $$$a_i,x_j\le K=10^6$$$. Отсортируем массивы $$$x,a$$$ по возрастанию и решим независимо для префикса, на котором $$$a_i\le K$$$, и для суффикса, на котором $$$a_i>K$$$. Заметим, что если $$$x_j>K$$$, то весь префикс станет нулями, поэтому для него количество можно будет не считать. Чтобы учесть ту часть, которая больше $$$K$$$, но при этом объединяется с подотрезком из части с $$$\le K$$$, можно взять наибольший элемент первой части $$$a_{i_0}$$$ и рассмотреть $$$\frac{a_{i_0}}{x_j}$$$, затем бинпоиском найти границы подотрезка с уже включенным подотрезком из второй части.
Чтобы решить задачу для $$$x_j\le K$$$ для суффикса, можно рассмотреть разности последовательных элементов. Если $$$a_{i+1}-a_i>K$$$, то они точно будут в разных классах. Поэтому поделим суффикс на подотрезки, который точно соответствуют разным классам в массиве $$$b$$$ и возьмем $$$c_i=a_i\mod p$$$ для нескольких рандомных $$$p\in[K,2\cdot K]$$$. Так как $$$\lfloor\frac{m_1+m_2}{n}\rfloor-(\lfloor\frac{m_1}{n}\rfloor+\lfloor\frac{m_2}{n}\rfloor)\le 1$$$, то при $$$m_1=p\cdot k,m_2=c_i,n=x_j$$$ получаем, что при подсчете для $$$c_i$$$ для какого-нибудь $$$p$$$ будет истинное значение (нужно из значений для всех $$$p$$$ выбрать наименьшее). А значения для разных $$$p$$$ считать обычным способом, только вместо префиксных сумм использовать дерево отрезков, чтобы можно было считать одновременно для всех подотрезков, которые точно находятся в разных классах.
Теперь перейдем к $$$x_j>K$$$. Для этого просто посчитаем границы подотрезков с разными классами перебором для $$$x=K$$$. Заметим, что границ будет не больше $$$\frac{a_{max}}{K}$$$. Пересчет границ при переходе от $$$x_j$$$ к $$$x_{j+1}$$$ можно делать бинпоиском, по $$$O(\log N)$$$ на каждую из границ. Итого, сложность $$$O(PK\log^2 K+\frac{a_{max}}{K}Q\cdot\log N)$$$, где $$$P$$$ — количество сгенерированных чисел $$$p$$$.