P6902: 栅栏涂色
传统题
1.000s
时间限制
256MB
内存限制
2 提交
0 解决
【题目描述】
【题目描述】
Bessie
最近收到了一套颜料，她想要给她的牧草地一端的栅栏上色。栅栏由 N
个 1 米长的小段组成（1≤N≤10^5
）。Bessie
可以使用 26 种不同的颜色，她将这些颜色由浅到深用字母 'A' 到 'Z' 标号（'A' 是很浅的颜色，'Z' 是很深的颜色）。从而她可以用一个长为 N 且每个字符均为字母的字符串来描述她想要给栅栏的每一小段涂上的颜色。
初始时，所有栅栏小段均未被上色。Bessie
一笔可以给任意连续若干小段涂上同一种颜色，只要她不会在较深的颜色之上涂上较浅的颜色（她只能用较深的颜色覆盖较浅的颜色）。
例如，一段长为 4
的未被涂色的栅栏可以按如下方式上色：
.... -> BBB. -> BBLL -> BQQL
由于时间紧迫，Bessie
认为她可能需要放弃为栅栏上某个连续的区间上色！现在，她正在考虑 Q 个候选的区间（1≤Q≤10^5
），每个区间用满足 1≤a≤b≤N
的两个整数 (a,b) 表示，为需要不上色的小段 a…b 的两端点位置。
对于每个候选区间，将所有区间外的栅栏小段都涂上所希望的颜色，并且区间内的栅栏小段均不涂色，最少需要涂多少笔？注意在这个过程中 Bessie
并没有真正进行任何的涂色，所以对于每个候选区间的回答是独立的。
【
输入格式】
（从终端/
标准输入读入）：
输入的第一行包含 N
和 Q。
下一行包含一个长为 N
的字符串，表示每个栅栏小段所希望的颜色。
以下 Q
行，每行包含两个空格分隔的整数 a 和 b，表示一个不涂色的候选区间。
【
输出格式】
（输出至终端/
标准输出）：
对于 Q
个候选区间的每一个，输出一行，包含答案。
【
输入样例】
：
8 2
ABBAABCB
3 6
1 4
【
输出样例】
：
4
3
【样例说明】
在这个样例中
，除去目标颜色 BAAB
所对应的区间，涂上颜色需要四笔，而除去 ABBA 仅需三笔。
.... -> AA.. -> ABBB -> ABCB
【
测试点性质】
：
测试点 1-4
满足 N,Q≤100。
测试点 5-7
满足 N,Q≤5000。
测试点 8-13
没有额外限制。