P16797 [Lanqiao Cup 2026 National B] Password Extraction

Xiao Lan found a digital password wall in some ruins. The password wall can be seen as a string $S$ of length $N$, and the string contains only digits from $0$ to $9$. Xiao Lan can take any non-empty contiguous substring of $S$ and treat this substring as a decimal integer. Leading zeros are allowed, and any number of leading zeros does not affect the final value. If the substring consists entirely of digit $0$, then no matter how long the substring is, its value is $0$. For example, the values of $05$ and $005$ are both $5$, and the values of $0$ and $00$ are both $0$. If two substrings have different start or end positions, then even if their values are the same, they are considered two different extraction plans. Now Xiao Lan has $M$ attempts. In the $i$-th attempt, a security threshold interval $[l_i, r_i]$ is given. For each attempt, please compute how many extraction plans make the extracted decimal value fall within $[l_i, r_i]$.

The first line contains two positive integers $N, M$, representing the length of the digit string and the number of queries. The second line contains a digit string $S$ of length $N$. The next $M$ lines each contain two integers $l_i, r_i$, representing the security threshold interval of one query.

Output $M$ lines. The $i$-th line outputs one integer, representing the number of valid extraction plans for the $i$-th query.

### Sample Explanation The string is $00510$. If we count all non-empty contiguous substrings by their values, we get: - Value $0$: there are $3$ extraction plans for substring $0$, and $1$ extraction plan for substring $00$, for a total of $4$ plans. - Value $1$: there is $1$ extraction plan for substring $1$. - Value $5$: the substrings $5$, $05$, and $005$ each have $1$ extraction plan, for a total of $3$ plans. - Value $10$: there is $1$ extraction plan for substring $10$. - Value $51$: the substrings $51$, $051$, and $0051$ each have $1$ extraction plan, for a total of $3$ plans. - Value $510$: the substrings $510$, $0510$, and $00510$ each have $1$ extraction plan, for a total of $3$ plans. Therefore, the answer for interval $[0, 5]$ is $4+1+3=8$. The answer for interval $[1, 10]$ is $1+3+1=5$. The answer for interval $[50, 510]$ is $3+3=6$. ### Constraints For $30\%$ of the testdata, $1 \le N, M \le 1000$. For $80\%$ of the testdata, $1 \le N, M \le 5000$. For all testdata, $1 \le N, M \le 10^6$, $0 \le l_i \le r_i \le 100000$. Translated by ChatGPT 5