1216E2 - Numerical Sequence (hard version)

Обозначим длину последовательности от 1 до $$$i$$$ как $$$L_{i}$$$, тогда $$$L_{i} = L_{i-1} + DigitSum(i)$$$, где $$$DigitSum(x)$$$ — функция, которая получает количество цифр в числе $$$x$$$. Мы знаем, что каждый раз $$$L_{i}$$$ растет на какое-то число $$$e = DigitSum(i)$$$, при чем это число меняется не так часто — только после того, как $$$i$$$ стало больше $$$9, 99, $$$ и т.д. В таком случае, если мы знаем длину последовательности, которая сейчас росла на $$$e = DigitSum(i)$$$, то как только $$$i$$$ станет больше 9, $$$e$$$ увеличится на 1, больше 99 — на 1, и так далее. В этих точках роста $$$e$$$ мы можем посчитать длину ряда, который у нас уже сейчас есть. Первой точкой в этом ряду будет 0. Далее мы можем воспользоваться формулой: $$$E_{i} = E_{i-1} + i\times{(10^{i} - 10^{i-1})}$$$. Такую таблицу до $$$R$$$ мы можем построить за $$$O(DigitSum(R))$$$ — такую табличку можно предподсчитать до начала обработки запросов, при чем $$$R$$$ будет не более $$$\sqrt{2k}$$$. Доказать это несложно — возьмем худший случай, в котором длина новой прицепляемой последовательности растёт ровно на 1 — в таком случае длина всей последовательности будет равной $$$\frac{n*(n-1)}{2}$$$, в нашем же случае — ситуация будет лучше. Обозначим предподсчитанную последовательность как $$$P$$$. По $$$P$$$ мы можем построить вторую последовательность $$$O$$$, где $$$O_{i}$$$ будет обозначать длину цельной последовательности (той, что 1121231234..), после которой мы будем прицеплять новую последовательность от $$$1$$$ до $$$K$$$, где $$$K = 10^{i}$$$. Первым элементом будет $$$0$$$, для каждого следующего несложно вывести формулу $$$cnt = (10^{i}-10^{i-1}), O_{i}=O_{i-1}+P_{i-1}*cnt+i*\frac{cnt*(cnt+1)}{2}$$$. По данной последовательности $$$O$$$ и заданному $$$k$$$ несложно определить, сколько цифр будет содержать каждый последний элемент прицепляемой к нашей последовательности — $$$O_{i}\leq{k}<{O_{i+1}}$$$. Зная начало первой последовательности, у которой последний элемент будет равен $$$10^{i}$$$ (это и есть $$$O_{i}$$$) мы можем вычислить смещение нашей последовательности относительно $$$O_{i}$$$. Все последовательности до $$$O_{i+1}$$$, начинающиеся после/в $$$O_{i}$$$ будут начинаться относительно $$$O_{i}$$$ в индексах $$$e\times{P_{i-1}}+i\times{\frac{e*(e+1)}{2}}$$$, где $$$e$$$ — номер последовательности. Таким образом, мы можем решить квадратное уравнение $$$e\times{P_{i-1}}+i\times{\frac{e*(e+1)}{2}}=absK$$$, где $$$absK=k-O_{i}$$$. Домножив всё на два мы получаем уравнение $$$2\times{e\times{P_{i-1}}}+i\times{e^{2}}+i\times{e}=2\times{absK} \Leftrightarrow i\times{e^{2}}+(2\times{P_{i-1}}+i)*e-2\times{absK}=0$$$. Таким образом, коэффициенты соответственно равны $$$a=i, b=2\times{P_{i-1}}+i, c=-2\times{absK}$$$. Решив его, берем корень $$$x_{1}=\frac{\sqrt{d}-b}{2a}$$$. Теперь, мы знаем сколько последовательностей началось до нас, значит, мы знаем и наш индекс в текущей последовательности — $$$curr = absK - (P_{i-1}*a_{1}+i\times\frac{a_1\times{(a_1+1)}}{2})$$$. Далее — мы можем определить, в диапазон каких чисел мы попали(по количеству цифр) — нам в этом поможет $$$P$$$ — тогда $$$P_j\leq{k}<P_{j+1}$$$, вычтя из $$$k$$$ $$$P_j$$$ мы получим число $$$u$$$, которое показывает в какую цифру среди записи чисел $$$10^i, 10^i+1, ..$$$ нам надо "тыкнуть". Таким образом, число, стоящее на месте, где находится $$$cur$$$ — это $$$10^i+(u-1)\div{j}$$$, а сама цифра в этом числе — $$$(u-1)\mod{j}$$$. если $$$u<10$$$, то следует вывести просто $$$u$$$, во избежания разбора дополнительных вариантов.

Решение — 61064504