#5731. 「NOISG 2026 Final」Gemstones

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2026 Final T4. Gemstones

你正在玩一款益智游戏，游戏中有 $n$ 颗排成一排的宝石，从左到右编号为 $1$ 到 $n$。第 $i$ 颗宝石的颜色为 $c[i]$。

在任何时刻，你都可以选择两颗颜色相同的相邻宝石并将其删除。随后，两边的宝石会向中间滑动以填补空隙，这可能会产生新的相邻同色宝石对。

你将面对 $q$ 个独立的情景。在第 $j$ 个情景中，你只考虑从第 $l[j]$ 颗到第 $r[j]$ 颗的宝石。假设你执行了最优的删除序列，请问最后剩下的宝石最少是多少颗？

输入格式

第一行包含两个以空格分隔的整数 $n$ 和 $q$。

第二行包含 $n$ 个以空格分隔的整数 $c[1], c[2], \ldots, c[n]$。

接下来的 $q$ 行，每行包含两个以空格分隔的整数。其中第 $i$ 行包含 $l[i]$ 和 $r[i]$。

输出格式

输出应包含 $q$ 行。其中第 $i$ 行应包含一个整数，即第 $i$ 个情景的答案。

样例 1

输入

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

输出

1
0
1
4

这 $n=8$ 颗宝石如下图所示。

在第一个情景中，只需考虑前三颗宝石。删除任何两颗相邻的同色宝石后都会剩下一颗宝石，之后无法再进行任何删除。因此，答案是 $1$。

在第二个情景中，可以按以下方式删除宝石，不留下任何宝石：

在第三个情景中，可以按以下方式删除宝石，剩下一颗宝石：

在第四个情景中，无法删除任何宝石。因此，答案是 $4$。

此样例满足子任务 $3,7,8$ 和 $9$ 的限制。

样例 2

输入

6 3
2 1 1 2 2 1
1 6
1 4
3 6

输出

2
0
0

此样例满足子任务 $3,6,7,8$ 和 $9$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 10^6$
• $0 \leq q \leq 500000$
• 对于所有 $1 \leq i \leq n$，$1 \leq c[i] \leq 10^9$
• 对于所有 $1 \leq j \leq q$，$1 \leq l[j] \leq r[j] \leq n$

详细子任务附加限制及分值如下表所示：