CF1860E Fast Travel Text Editor

给定一个由小写拉丁字母组成的字符串 $s$。 有一个光标，初始时位于字符串中两个相邻字母之间。光标不能放在第一个字母之前或最后一个字母之后。 每次操作，你可以执行以下三种操作之一： - 将光标向左移动一个位置（前提是不会移到第一个字母之前）； - 将光标向右移动一个位置（前提是不会移到最后一个字母之后）； - 设光标左侧的字母为 $x$，右侧的字母为 $y$。你可以选择字符串中任意一对相邻的字母，其中左侧为 $x$，右侧为 $y$，并将光标移动到这两个字母之间的位置。 你将会被询问 $m$ 次，每次询问给出两个整数 $f$ 和 $t$，分别表示光标的初始位置和目标位置。对于每个询问，请计算将光标从位置 $f$ 移动到位置 $t$ 所需的最少操作次数。

第一行包含一个字符串 $s$（$2 \le |s| \le 5 \times 10^4$），仅由小写拉丁字母组成。 第二行包含一个整数 $m$（$1 \le m \le 5 \times 10^4$），表示询问的数量。 接下来的 $m$ 行，每行包含两个整数 $f$ 和 $t$（$1 \le f, t \le |s| - 1$），表示第 $i$ 次询问中光标的初始位置和目标位置。位置 $x$ 表示光标位于字符串第 $x$ 个和第 $x+1$ 个字母之间（下标从 $1$ 开始）。

对于每个询问，输出一行一个整数，表示将光标从位置 $f$ 移动到位置 $t$ 所需的最少操作次数。

由 ChatGPT 4.1 翻译