CF1886C Decreasing String

回忆一下，如果字符串 $a$ 是字符串 $b$ 的前缀（且 $a \ne b$），或者存在某个下标 $i$（$1 \le i \le \min(|a|, |b|)$）使得 $a_i < b_i$，并且对于任意下标 $j$（$1 \le j < i$）都有 $a_j = b_j$，那么字符串 $a$ 在字典序上小于字符串 $b$。 现在给定一个由小写拉丁字母组成的字符串序列 $s_1, s_2, \dots, s_n$。字符串 $s_1$ 已经给出，其他字符串按照如下规则生成：要得到字符串 $s_i$，从字符串 $s_{i-1}$ 中删除一个字符，使得得到的字符串 $s_i$ 在字典序上最小。 例如，如果 $s_1 = \mathrm{dacb}$，那么 $s_2 = \mathrm{acb}$，$s_3 = \mathrm{ab}$，$s_4 = \mathrm{a}$。 接下来我们得到字符串 $S = s_1 + s_2 + \dots + s_n$（$S$ 表示所有字符串 $s_1, s_2, \dots, s_n$ 的拼接）。 你需要输出字符串 $S$ 的第 $pos$ 个字符（即 $S_{pos}$）。

第一行包含一个整数 $t$，表示测试用例的数量（$1 \le t \le 10^4$）。 每个测试用例包含两行。第一行是字符串 $s_1$（$1 \le |s_1| \le 10^6$），由小写拉丁字母组成。第二行包含一个整数 $pos$（$1 \le pos \le \frac{|s_1| \cdot (|s_1| + 1)}{2}$）。你可以认为 $n$ 等于给定字符串的长度（$n = |s_1|$）。 输入的额外限制：所有测试用例中 $|s_1|$ 的总和不超过 $10^6$。

对于每个测试用例，输出答案——即字符串 $S$ 的第 $pos$ 个字符。注意，不同测试用例的答案之间不需要用空格或换行分隔。

由 ChatGPT 4.1 翻译