CF238D Tape Programming

有一种编程语言，其中每个程序都是由“”和数字组成的非空序列。下面解释一下这种语言的解释器是如何工作的。程序的执行依赖于指令指针（IP）的移动，指令指针包含两个部分： - 当前字符指针（CP）； - 方向指针（DP），可以指向左或右； 最开始时，CP 指向序列的最左边字符，DP 指向右。 我们重复以下步骤，直到 CP 首次指向序列之外的位置为止： - 如果 CP 指向的是一个数字，解释器会打印该数字，然后 CP 按照 DP 的方向移动一步。之后，该数字在序列中的值减一。如果打印的是 $0$，那么它无法再减少，因此会被从序列中删除，序列长度减少 $1$。 - 如果 CP 指向的是“”，则 DP 的方向会分别变为“左”或“右”。然后，CP 根据 DP 的方向移动一步。如果新指向的字符依然是“”，那么之前的字符会从序列中被删除。 如果 CP 在任何时刻移出序列，程序执行终止。 很明显，这种语言中的每个程序都能在有限步后终止。 现有一个由“”和数字组成的序列 $s_{1},s_{2},…,s_{n}$。你需要回答 $q$ 个询问。每个询问给出 $l$ 和 $r$，询问你如果将子序列 $s_{l},s_{l+1},…,s_{r}$ 作为独立的程序运行，那么每个数字会被打印多少次。

输入的第一行包含两个整数 $n$ 和 $q$，$1 \leq n, q \leq 10^{5}$，分别表示序列 $s$ 的长度和询问数。 第二行包含序列 $s$，由“”和数字（0..9）组成，从左到右排列。注意，$s$ 的字符之间没有空格。 接下来的 $q$ 行每行包含两个整数 $l_{i}$ 和 $r_{i}$，$1 \leq l_{i} \leq r_{i} \leq n$，表示第 $i$ 次询问的区间。

对于每一个询问，输出 $10$ 个用空格分隔的整数：$x_{0},x_{1},…,x_{9}$，其中 $x_{i}$ 表示运行这个子程序时打印了多少次数字 $i$。按输入顺序输出每个询问的答案。

由 ChatGPT 5 翻译