Який порядок дає максимум. Класичний результат: щоб конкатенація набору чисел була найбільшою, треба відсортувати їх компаратором
де — склеювання десяткових записів. Рівносильне й зручніше формулювання: порівнюємо нескінченні повторення та vvv\ldots лексикографічно. Наприклад, 9 \prec 89, бо 999\ldots > 898\ldots
Виписати сам порядок неможливо — чисел до 10^{17}. Але кожен запит — це «яка цифра стоїть на позиції », тож достатньо вміти для довільного швидко сказати, скільки цифр стоїть перед .
Скільки чисел випереджають . Розіб'ємо за довжиною запису. Зафіксуємо довжину і запитаємо: які з рівно цифрами йдуть перед ? З опису через нескінченні повторення випливає простий критерій. Нехай P_L(x) — перші цифр рядка , прочитані як число. Тоді
причому поріг збільшуємо на одиницю, якщо саме P_L(x) ще не випереджає (це трапляється, коли не кратне довжині і «обрізане» повторення програє). Отже всередині кожного класу довжини множина випереджальних чисел — це просто суфікс числового відрізка, і його розмір рахується за :
Сумуючи \mathrm{cnt}_L отримуємо ранг , а сумуючи L \cdot \mathrm{cnt}_L — позицію першої цифри у відповіді. Порогів усього \mathcal{O}(\log b).
Однакові числа за компаратором (як і ) утворюють «нічию»; будь-яке впорядкування таких дає той самий рядок, тож достатньо зафіксувати довільне правило (скажімо, більше число раніше) і не хвилюватися.
Відповідь на запит. Позиція першої цифри монотонно спадає зі зростанням числа в межах одного класу довжини (більші числа стоять раніше). Тому в кожному класі двійковим пошуком знаходимо число з найбільшою стартовою позицією, що не перевищує ; серед класів беремо кандидата з найбільшим рангом — це і є число, всередину якого потрапляє позиція . Далі лишається відняти стартову позицію й вивести відповідну цифру.
Дрібниця, що прискорює. Пороги P_L(x) для різних — вкладені префікси одного нескінченного рядка, тому межу для довжини L-1 отримуємо з межі для звичайним діленням на . Це дозволяє не запускати повний двійковий пошук у кожному класі окремо.
Обережно з переповненням. Порівняння і через числа дає до цифр — потрібен __int128 (або порівняння рядків).
Складність — \mathcal{O}\bigl(q \log^2 b\bigr) операцій, пам'ять \mathcal{O}(\log b).