P15850 [NOISG 2026 Finals] 宝石 / 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 解释 $n = 8$ 颗宝石如下图所示。 :::align{center}  ::: 在第一个场景中，只考虑前三个宝石。删除任意两个相邻的宝石后，会恰好剩下一颗宝石，之后无法再进行任何删除。因此，答案是 $1$。 在第二个场景中，可以按以下方式删除宝石，最终一颗不剩： :::align{center}  ::: 在第三个场景中，可以按以下方式删除宝石，最终剩下一颗： :::align{center}  ::: 在第四个场景中，无法删除任何宝石。因此，答案是 $4$。 ### 子任务 对于所有测试用例，输入数据满足以下限制： - $1 \le n \le 10^6$ - $1 \le q \le 500\,000$ - 对于所有 $1 \le i \le n$，有 $1 \le c[i] \le 10^9$ - 对于所有 $1 \le j \le q$，有 $1 \le l[j] \le r[j] \le n$ 你的程序将在满足以下限制的输入实例上进行测试： | 子任务 | 分数 | 额外约束条件 | |:-------:|:-----:|:----------------------:| | 0 | 0 | 样例测试用例 | | 1 | 2 | $c[1] = c[2] = \cdots = c[n]$ | | 2 | 5 | 相同颜色的宝石形成一个连续的子数组（如果 $c[i] = c[j]$ 且 $i < j$，那么 $c[i] = c[i+1] = \cdots = c[j]$） | | 3 | 9 | $n, q \le 2000$ | | 4 | 4 | 对于所有 $1 \le j \le q$，有 $l[j] = 1$ | | 5 | 8 | 每种颜色恰好有两颗宝石 | | 6 | 16 | 对于所有 $1 \le i \le n$，有 $c[i] \le 2$ | | 7 | 18 | $n, q \le 100\,000$ | | 8 | 15 | $n, q \le 300\,000$ | | 9 | 23 | 无额外约束 | 翻译由 DeepSeek V3.2 完成