QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 5173. 染色

统计

题目描述

给定一张纸条,纸条上依次有 $n$ 个格子,第 $i$ 个格子的颜色是 $a_i$。

现在小 A 每秒钟可以进行以下两种操作之一。

将某个格子染成一种颜色。

移动到相邻的格子,前提要求移动前和移动后的两个格子的颜色相同。

现在小 A 想在纸条上移动,但是他不想花费太多时间,所以他会询问你 $Q$ 个问题。第 $i$ 个问题是从格子 $u_i$ 移动到 $v_i$ 最少需要的时间。

注意,每个问题之间是独立的,意味着不需要真正对纸条进行染色。

输入格式

第一行两个正整数 $n, Q$ 分别表示纸条长度和询问次数。

接下来一行 $n$ 个正整数,第 $i$ 个数表示纸条上第 $i$ 个格子的颜色 $a_i$。

接下来 $Q$ 行,每行两个正整数 $u_i,v_i$,表示询问从 $u_i$ 到 $v_i$ 的最少时间秒数。

输出格式

输出 $Q$ 行,每行一个整数表示对应询问的答案。

样例输入 #1

5 4
2 2 3 1 3
1 5
2 4
5 2
3 3

样例输出 #1

6
4
5
0

数据范围与约定

对于 $100\%$ 的数据,保证 $1\le u_i,v_i\le n\le 10^6,1\le Q\le 10^6,1\le a_i\le m\le n$。

对于子任务 $1$($3 $分),保证 $n\le 10^4,Q,m\le 100$。

对于子任务 $2$($13$ 分),保证 $n,Q\le 10^5,m\le 3$。

对于子任务 $3$($18$ 分),保证 $n,Q\le 5000$。

对于子任务 $4$($66$ 分),无特殊限制。