Fast Travel Text Editor
题意翻译
给出一个字符串 $s$ (全为小写字母,长度为 $n$ )。有一个光标在任意两个字符之间(不能出现在第一个字符之前和最后一个字符之后)。
有三种操作,代价均为 $1$ :
- 将光标向左移一位(不能出现在第一个字符之前)。
- 将光标向右移一位(不能出现在最后一个字符之后)。
- 若有两对相同的字符对,光标便可从一个字符对之间移动到另一个字符对之间。
有 $m$ 组询问。每组询问给出两个整数 $f$ 和 $t$ ,求光标从 $f$ 移动到 $t$ 的最小代价。
题目描述
You are given a string $ s $ , consisting of lowercase Latin letters.
There's a cursor, initially placed between two adjacent letters of the string. The cursor can't be placed before the first or after the last letter.
In one move, you can perform one of three actions:
- move a cursor one position to the left (if that doesn't place it before the first letter);
- move a cursor one position to the right (if that doesn't place it after the last letter);
- let $ x $ be the letter immediately to the left of the cursor, and $ y $ be the letter immediately to the right of the cursor. Choose any pair of adjacent letters in the string such that the left of them is $ x $ and the right of them is $ y $ , and move the cursor to the position between these two letters.
You are asked $ m $ queries. In each query, you are given two integers $ f $ and $ t $ , which correspond to two valid positions of the cursor in the string. In response to the query, you have to calculate the minimum number of operations required to move the cursor from position $ f $ to position $ t $ .
输入输出格式
输入格式
The first line contains a string $ s $ ( $ 2 \le |s| \le 5 \cdot 10^4 $ ), consisting of lowercase Latin letters.
The second line contains a single integer $ m $ ( $ 1 \le m \le 5 \cdot 10^4 $ ) — the number of queries.
The $ i $ -th of the next $ m $ lines contains two integers $ f $ and $ t $ ( $ 1 \le f, t \le |s| - 1 $ ) — the initial and the target positions of the cursor in the $ i $ -th query. Position $ x $ means that the cursor is between the $ x $ -th and the $ (x+1) $ -st letters of the string ( $ 1 $ -indexed).
输出格式
For each query, print the minimum number of actions required to move the cursor from position $ f $ to position $ t $ .
输入输出样例
输入样例 #1
codecode
3
1 7
3 5
3 6
输出样例 #1
3
2
2
输入样例 #2
abcdefghij
3
1 9
9 1
5 5
输出样例 #2
8
8
0
输入样例 #3
aaaaaaaaaaaa
4
10 8
3 7
6 1
11 11
输出样例 #3
1
1
1
0