A6175 | $Colored Portals$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

一条直线上有 $n$ 个城市，这些城市的编号为 $1$ 到 $n$。 传送门被用于在城市间移动，传送门有四种颜色：蓝色，绿色，红色和黄色。每一个城市都有两种颜色的传送门。你可以从城市 $i$ 到城市 $j$，当且仅当这两个城市存在同色的传送门（例如，你可以从有红色和蓝色的传送门的城市到有蓝色和绿色传送门的城市），花费 $|i - j|$ 个硬币。 你的任务是回答 $q$ 个询问：计算城市 $x$ 到城市 $y$ 的最小花费。

第一行输入 $t$（$1\le t \le 10^4$），代表测试数据的组数。 对于每个测试数据，第一行输入 $n,q$（$1\le n,q \le2 \times 10^5$），表示城市数和询问数。 第二行输入 $n$ 个只能为 BG，BR，BY，GR，GY，RY 之一的字符串，第 $i$ 个表示城市 $i$ 有的传送门颜色，B 表示蓝色，G 表示绿色，R 表示红色，Y 表示黄色。 接下来 $q$ 行第 $j$ 行输入 $x_j,y_j$（$1 \le x_j,y_j \le n$），表示第 $j$ 个询问的 $x,y$。 输入保证所有测试数据中 $n$ 的和不超过 $2 \times 10^5$，$q$ 的和不超过 $2 \times 10 ^ 5$。

对每个询问，输出一个整数，即从城市 $x$ 到城市 $y$ 的最小花费（若无解输出 $-1$）。

输入 #1

2
4 5
BR BR GY GR
1 2
3 1
4 4
1 4
4 2
2 1
BG RY
1 2

输出 #1

C++ 编辑器

输入

输出