No Time to Dry

题目描述

Bessie 最近收到了一套绘画工具，她想给牧场一端的长栅栏上色。栅栏由 $N$ 个连续的 1 米线段组成（$1\le N\le 2\cdot 10^5$）。Bessie 有 $N$ 种不同的颜色可用，她用字母 $1$ 到 $N$ 标记这些颜色，并按颜色深浅递增排序（$1$ 非常浅，$N$ 非常深）。因此，她可以用一个包含 $N$ 个整数的数组来描述她希望给每段栅栏涂上的目标颜色。

起初，所有栅栏段都未上色。Bessie 每次刷漆可以用一种颜色给任意一个连续区间的线段上色，但前提是她永远不会在较深的颜色上覆盖较浅的颜色（她只能用更深的颜色覆盖更浅的颜色）。 例如，一个初始未上色、长度为 4 的线段可以按如下方式上色： 0000 -> 1110 -> 1122 -> 1332

不幸的是，Bessie 不想浪费时间等油漆变干。因此，她认为自己可能需要让一些栅栏段不被涂色！目前，她正在考虑 $Q$ 个候选区间（$1\le Q\le 2\cdot 10^5$），每个区间由两个整数 $(a,b)$ 描述，其中 $1 \leq a \leq b \leq N$ 表示要涂色的线段范围 $a \ldots b$ 的两个端点下标。

对于每个候选区间，要求在使区间内每个栅栏段都被涂成其目标颜色、且区间外所有栅栏段保持未上色的前提下，最少需要多少次刷漆？注意：Bessie 在这个过程中并不会真的去涂色，因此每个候选区间的答案彼此独立。

输入格式

第一行包含 $N$ 和 $Q$。 第二行包含一个长度为 $N$ 的整数数组，表示每段栅栏的目标颜色。 接下来 $Q$ 行每行包含两个用空格分隔的整数 $a$ 和 $b$，表示一个可能要涂色的候选区间。

输出格式

对于这 $Q$ 个候选区间中的每一个，输出一行答案。

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

2
3
3
3

提示

在这个例子中，对应目标图案 1 1 2 的子区间需要两次刷漆。对应目标图案 2 1 1 2 的子区间需要三次刷漆。对应目标图案 1 2 2 1 1 2 的子区间需要三次刷漆。对应目标图案 1 2 3 2 的子区间需要三次刷漆。

评分： 测试点 1-2 满足 $N,Q\le 100$。 测试点 3-5 满足 $N,Q\le 5000$。 在测试点 6-10 中，输入数组中不包含大于 $10$ 的整数。 测试点 11-20 没有额外限制。

题目鸣谢：Andi Qu、Brian Dean、Benjamin Qi

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum