P4384 [Eight Provinces Joint Exam 2018] Zhi Hu Cuan

For a string $s$, define $|s|$ to denote the length of $s$. Next, define $s_i$ as the $i$-th character of $s$, and $s_{l,r}$ as the string formed by concatenating, from left to right, the $l$-th through the $r$-th characters of $s$. In particular, if $l \gt r$, or $l \notin [1, |s|]$, or $r \notin [1, |s|]$, we consider $s_{l,r}$ to be the empty string. Given a string $s$ of length $n$ consisting only of digits, there are $q$ queries. In the $k$-th query, a substring $s_{l,r}$ of $s$ is given. For this substring, count the number of pairs $(i, j)$ such that $1 \le i \lt j \le n$, $i + 1 < j$, and $s_{l,r}$ occurs in $s_{1,i}$ or in $s_{i+1,j-1}$ or in $s_{j,n}$.

The first line contains two integers, the string length $n$ and the number of queries $q$. The second line contains a string of length $n$ consisting only of digit characters, representing $s$. Each of the next $q$ lines contains two positive integers $l$ and $r$, indicating that the queried substring is $s_{l,r}$.

For each query, output a single integer on its own line representing the answer.

| Test point | $n$ | $q$ | Other conditions | | :------------: | :---------: | :---------: | :-------------------------------------------: | | $1$ | $=50$ | $=100$ | None | | $2 \sim 3$ | $=300$ | $=300$ | None | | $4 \sim 5$ | $=2000$ | $=3000$ | None | | $6 \sim 9$ | $=100000$ | $=100000$ | $\sum \lvert s_{l,r} \rvert \le 10^6$ | | $10 \sim 12$ | $=30000$ | $=50000$ | None | | $13$ | $=100000$ | $=100000$ | The string $s$ contains only $0$. | | $14 \sim 20$ | $=100000$ | $=300000$ | None | For all testdata, $1 \le n \le 10^5$, $1 \le q \le 3 \times 10^5$, $1 \le l \le r \le n$, and $s$ contains only digit characters. Translated by ChatGPT 5