比赛场次 485
比赛名称 USACO水题大战
比赛状态 已结束比赛成绩
开始时间 2021-04-03 20:00:00
结束时间 2021-04-09 22:00:00
开放分组 全部用户
注释介绍 省选加油!
题目名称 No Time to Dry
输入输出 dry.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分

No Time to Dry

★★★☆   输入文件:dry.in   输出文件:dry.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

$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$,表示一个需要涂色的候选区间。

【输出格式】

对于 $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说明】

在这个样例中,

对应颜色为$ \{1,1,2\} $的子段涂上颜色需要 $2$ 笔。

对应颜色为$ \{2,1,1,2\} $的子段涂上颜色需要 $3$ 笔。

对应颜色为$ \{1,2,2,1,1,2\} $的子段涂上颜色需要 $3$ 笔。

对应颜色为$ \{1,2,3,2\} $的子段涂上颜色需要 $3$ 笔。

【样例2/3输入输出】

点击下载样例2/3

【数据规模与约定】

测试点 $1 \sim 2$ 满足 $N,Q \le 100$。

测试点 $3 \sim 5$ 满足 $N,Q \le 5000$。

测试点 $6 \sim 10$ 中,输入数组不包含大于 $10$ 的数。

测试点 $11 \sim 20$ 没有额外限制。

【来源】

$USACO$ 二月公开赛 $Platinum$ 组