P6385 "MdOI R2" Little Goth

Little M and Little B are a pair of good friends, and they really like hiking.

A mountain can be abstracted as a string $S$ of length $n$, containing only lowercase letters. For a string $S$, we define $|S|$ as the length of the string, and $S_{L\ldots R}$ as the string formed by concatenating, from left to right, the $L$-th character to the $R$-th character in $S$. Little M starts at position $i$, and she wants to reach the peak at position $k$, while Little B will help her. To do this, they need to perform a sequence of operations. They **must** use the teleportation magic circle at position $p$ **exactly once** before all operations. By casting the spell, Little B's position can be changed to any $j$ satisfying $j \geq i$ and $S_{i \ldots j} = S_{p \ldots p + (j-i)}$. At the same time, they need to pay a cost of $n-j$. It is guaranteed that such a $j$ exists. After that, suppose Little M and Little B are at positions $i$ and $j$, respectively. They may perform any number of times one of the following operations: - Let Little M climb, i.e. set $i=i+1$ or $i=i-1$. If after this operation $i>j$, then set $j=i$. - Let Little B climb, i.e. set $j=j+1$ or $j=j-1$. If after this operation $i>j$, then set $i=j$. - Use "Spiral Ascension". Specifically, choose two indices $l$ and $r$ such that $S_{l \ldots r} = S_{i \ldots j}$, then set $i=l,j=r$. For some reason, after each operation, it must be guaranteed that $1 \leq i , j \leq n$. Performing any one of the above operations costs $1$. Hiking is tiring, so they want to know the minimum total cost needed to make Little M reach the peak, i.e. make $i=k$. Also, because they like hiking very much, they have many queries to ask you.

The first line contains two integers $n$ and $q$, representing the length of the string $S$ and the number of queries. The second line contains a string $S$ of length $n$, consisting only of lowercase letters. The next $q$ lines each contain three integers $i,p$ and $k$, indicating Little M's position, the teleportation magic circle position, and the peak position.

Output $q$ lines in total. The $i$-th line contains an integer, representing for the $i$-th query with given $i,p$ and $k$, the minimum total cost needed to make Little M reach the peak, i.e. make Little M's position $i=k$.

【Help and Hints】 To make it easier for contestants to test their code, this problem additionally provides an extra sample for contestants to use. [Sample Input](https://www.luogu.com.cn/paste/j7u8z9ir) [Sample Output](https://www.luogu.com.cn/paste/fh19p0a4) -------- 【Sample Explanation】 For the first query in the sample, when using the teleportation spell, we can only set $j=5$, paying a cost of $8-5=3$. After that, first use the third type of operation once, choosing $l=2,r=2$ and setting $i=l,j=r$, then use the first type of operation once, setting $i-1$, and thus make $i=k$. The total cost is $5$. For the second query, we can choose $j=2$, paying a cost of $8-2=6$, then use the third type of operation once, choosing $l=4,r=5$ and setting $i=l,j=r$, and then perform the first type of operation once, setting $i+1$, to make $i=k$. The total cost is $8$. --- 【Constraints】 **This problem uses bundled testdata.** For all testdata, it is guaranteed that $1 \leq n,q \leq 3\times 10^4$, and $S$ contains only lowercase letters. | Subtask ID | $n\leq$ | $q \leq$ | Special Property | Score | Time Limit | | :--------: | :---------------: | :---------------: | :---------------------: | :---: | :--------: | | Subtask 1 | $15$ | $15$ | None | $3$ | 1s | | Subtask 2 | $80$ | $80$ | None | $14$ | 1s | | Subtask 3 | $2 \times 10^4$ | $2 \times 10^4$ | $S$ contains only `a` | $8$ | 3s | | Subtask 4 | $2 \times 10^4$ | $2 \times 10^4$ | $S_1$ | $7$ | 3s | | Subtask 5 | $400$ | $400$ | None | $9$ | 1s | | Subtask 6 | $2\times 10^4$ | $2 \times 10^4$ | All queries have the same $k$ | $10$ | 3s | | Subtask 7 | $10^3$ | $10^3$ | None | $10$ | 2s | | Subtask 8 | $1.5 \times 10^4$ | $1.5 \times 10^4$ | None | $11$ | 3s | | Subtask 9 | $3 \times 10^4$ | $3 \times 10^4$ | None | $28$ | 3s | Property $S_1$ is: for a given $p$, the $j$ that satisfies the condition is unique. Translated by ChatGPT 5