P13971 [VKOSHP 2024] Exploration Robots

用于测试机器人的场地由 $n$ 个格子组成，这些格子从左到右依次编号为 $1$ 到 $n$。每个格子中包含一个英文字母，从第一个格子到第 $n$ 个格子依次读出这些字母可以得到字符串 $s$。 有两个机器人可以在场地上移动，具体规则如下： - 机器人知道字符串 $s$； - 机器人可以自由交换信息； - 机器人始终知道它们之间的距离，以及哪一个在左、哪一个在右； - 每个机器人可以读取正下方格子的字母； 每一步，机器人可以在与另一个机器人交换信息后，移动到相邻的左侧或右侧格子。如果机器人试图移动到第一个格子左侧或第 $n$ 个格子的右侧，则会被销毁。 科学家们要进行 $q$ 次实验，在第 $i$ 次实验中，第一个机器人被放置在位置 $x_i$，第二个机器人被放置在位置 $y_i$。每次实验中，机器人的目标是尽可能多地访问不同的格子。对于每次实验，需要确定机器人在不冒被销毁风险的情况下，最多能访问多少个不同的格子。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 300\,000$），分别表示格子的数量和实验的次数。 第二行包含长度为 $n$ 的字符串 $s$，由 $n$ 个小写拉丁字母组成。 接下来的 $q$ 行，每行包含一对整数 $x_i, y_i$（$1 \le x_i, y_i \le n$）。

对于每次实验，输出机器人能够访问的不同格子的最大数量。

考虑示例中的最后一次实验。两个机器人从同一个位置出发，看到的字母是 $\texttt{a}$。它们明白向左移动是危险的，因为可能导致机器人被销毁。然而，向右移动是安全的，因为字符串的最后一个字母是 $\texttt{b}$。一个或两个机器人向右移动，直到到达字母 $\texttt{b}$。到达 $\texttt{b}$ 时，机器人知道之前的字符串是 $\texttt{aab}$，这可能是字符串的开头或结尾；它们无法越界，否则会被销毁，因此它们总共访问了 $3$ 个格子。 由 ChatGPT 4.1 翻译