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}}$$$.