1006. 颜色不同距离翻倍

题目描述

有一个包含 $N$ 个顶点的带权完全无向图，顶点编号为 $1,2,\ldots,N$。

每个顶点 $i$ 有一个类型 $A_i$。对于任意两个不同的顶点 $X,Y$，无向边 $(X,Y)$ 的权值定义如下：

• 如果 $A_X=A_Y$，边权为 $|X-Y|$；
• 如果 $A_X\ne A_Y$，边权为 $2|X-Y|$。

共有 $Q$ 次询问。每次询问给定两个顶点 $X,Y$，求从顶点 $X$ 到顶点 $Y$ 的最短路长度。

两个顶点之间的最短路长度定义为：所有从 $X$ 到 $Y$ 的路径中，路径经过的边权之和的最小值。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

每组测试数据的格式如下：

第一行输入两个整数 $N,Q$，分别表示顶点数量和询问数量。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$，其中 $A_i$ 表示顶点 $i$ 的类型。

接下来 $Q$ 行，每行输入两个整数 $X,Y$，表示一次询问。

对于一组测试数据：

$2\le N\le 4\times 10^4$；

$1\le Q\le 2\times 10^6$；

$1\le A_i\le 20$；

$1\le X,Y\le N$。

OJ 中只有一个正式测试点，该测试点满足：

$T=100$；

$\sum N=3\times 10^5$；

$\sum Q=10^7$。

输出格式

对于每组测试数据，输出一行 $Q$ 个整数，依次表示每次询问的最短路长度。

同一行中相邻两个整数之间用一个空格分隔。

样例输入

3
6 8
1 4 2 1 3 3
6 1
4 6
6 4
4 4
3 5
4 6
4 2
2 3
10 9
3 1 1 2 2 4 3 3 5 1
4 1
3 4
2 5
9 3
6 7
6 10
10 5
7 1
4 10
4 3
1 2 1 2
1 3
2 4
1 4

样例输出

6 3 3 0 4 3 4 2
5 2 4 9 2 7 9 6 9
2 2 4

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1006