A6427. 「USACO 2021.2 Platinum」No Time to Dry
编程题
提高+/省选-
知识点
题目描述
**题目来自 [USACO 2021 February Contest, Platinum](http://usaco.org/index.php?page=feb21results) Problem 1. [No Time to Dry](http://usaco.org/index.php?page=viewproblem2&cpid=1116&lang=zh)。**
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 没有足够的时间等待颜料变干。所以，Bessie 认为她可能需要放弃为栅栏上某些小段上色！现在，她正在考虑 $Q$ 个候选的区间（$1\le Q\le 2\cdot 10^5$），每个区间用满足 $1 \leq a \leq b \leq N$ 的两个整数 $(a,b)$ 表示，为需要上色的小段 $a \ldots b$ 的两端点位置。
对于每个候选区间，将所有区间内的栅栏小段都涂上所希望的颜色，并且区间外的栅栏小段均不涂色，最少需要涂多少笔？注意在这个过程中 Bessie 并没有真正进行任何的涂色，所以对于每个候选区间的回答是独立的。
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 没有足够的时间等待颜料变干。所以，Bessie 认为她可能需要放弃为栅栏上某些小段上色！现在，她正在考虑 $Q$ 个候选的区间（$1\le Q\le 2\cdot 10^5$），每个区间用满足 $1 \leq a \leq b \leq N$ 的两个整数 $(a,b)$ 表示，为需要上色的小段 $a \ldots b$ 的两端点位置。
对于每个候选区间，将所有区间内的栅栏小段都涂上所希望的颜色，并且区间外的栅栏小段均不涂色，最少需要涂多少笔？注意在这个过程中 Bessie 并没有真正进行任何的涂色，所以对于每个候选区间的回答是独立的。
输入格式
输入的第一行包含 $N$ 和 $Q$。
下一行包含一个长为 $N$ 的整数数组，表示每个栅栏小段所希望的颜色。
以下 $Q$ 行，每行包含两个空格分隔的整数 $a$ 和 $b$，表示一个需要涂色的候选区间。
下一行包含一个长为 $N$ 的整数数组，表示每个栅栏小段所希望的颜色。
以下 $Q$ 行，每行包含两个空格分隔的整数 $a$ 和 $b$，表示一个需要涂色的候选区间。
输出格式
对于 $Q$ 个候选区间的每一个，输出一行，包含答案。
输入输出样例
输入 #1
8 4 1 2 2 1 1 2 3 2 4 6 3 6 1 6 5 8
输出 #1
2 3 3 3
说明/提示
- 测试点 $1\sim 2$ 满足 $N,Q\le 100$。
- 测试点 $3\sim 5$ 满足 $N,Q\le 5000$。
- 测试点 $6\sim 10$ 中，输入数组不包含大于 $10$ 的数。
- 测试点 $11\sim 20$ 没有额外限制。
- 测试点 $3\sim 5$ 满足 $N,Q\le 5000$。
- 测试点 $6\sim 10$ 中，输入数组不包含大于 $10$ 的数。
- 测试点 $11\sim 20$ 没有额外限制。