CF1216E2 Numerical Sequence (hard version)

本题的简单版与困难版唯一的区别在于 $k$ 的最大值。 你有一个无限序列，其形式为“112123123412345\dots”，由所有连续正整数的块首尾相连组成。第一个块包含从 $1$ 到 $1$ 的所有数字，第二个块包含从 $1$ 到 $2$，第三个块包含从 $1$ 到 $3$，以此类推，第 $i$ 个块包含从 $1$ 到 $i$ 的所有数字。 因此，序列的前 $56$ 个元素为“11212312341234512345612345671234567812345678912345678910”。序列中的元素从 $1$ 开始编号。例如，第 $1$ 个元素是 $1$，第 $3$ 个元素是 $2$，第 $20$ 个元素是 $5$，第 $38$ 个元素是 $2$，第 $56$ 个元素是 $0$。 你的任务是回答 $q$ 个独立的询问。在第 $i$ 个询问中，给定一个整数 $k_i$，请计算序列中第 $k_i$ 个位置上的数字。

输入的第一行包含一个整数 $q$（$1 \leq q \leq 500$），表示询问的数量。 接下来的 $q$ 行中，第 $i$ 行包含一个整数 $k_i$（$1 \leq k_i \leq 10^{18}$），表示第 $i$ 个询问。

输出 $q$ 行，每行输出一个数字 $x_i$（$0 \leq x_i \leq 9$），表示第 $i$ 个询问的答案，即序列中第 $k_i$ 个位置上的数字。

第一个样例中的答案已在题目描述中给出。 由 ChatGPT 4.1 翻译