#PU1087. USACO 2021 January Contest, Silver — Problem 2. No Time to Paint

    ID: 1477 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:jan21来源:usaco.orgscoring:equal_test_cases线段树分块

USACO 2021 January Contest, Silver — Problem 2. No Time to Paint

USACO 2021 January Contest, Silver — Problem 2. No Time to Paint

题目描述

Bessie has recently received a painting set, and she wants to paint the long fence at one end of her pasture. The fence consists of NN consecutive 1-meter segments (1≤N≤1051\le N\le 10^5). Bessie has 26 different colors available, which she labels with the letters 'A' through 'Z' in increasing order of darkness ('A' is a very light color, and 'Z' is very dark). She can therefore describe the desired color she wants to paint each fence segment as a length-NN string where each character is a letter. Initially, all fence segments are uncolored. Bessie can color any contiguous range of segments with a single color in a single brush stroke as long as she never paints a lighter color over a darker color (she can only paint darker colors over lighter colors). For example, an initially uncolored segment of length four can be colored as follows: .... -> BBB. -> BBLL -> BQQL Running short on time, Bessie thinks she may need to leave some consecutive range of fence segments unpainted! Currently, she is considering QQ candidate ranges (1≤Q≤1051\le Q\le 10^5), each described by by two integers (a,b)(a,b) with 1≤a≤b≤N1 \leq a \leq b \leq N giving the indices of endpoints of the range a…ba \ldots b of segments to be left unpainted. For each candidate range, what is the minimum number of strokes needed to paint every fence segment outside those in the range with its desired color while leaving all fence segments inside the range uncolored? Note that Bessie does not actually do any painting during this process, so the answers for each candidate range are independent.

输入格式

The first line contains NN and QQ. The next line contains a string of length NN characters representing the desired color for each fence segment. The next QQ lines each contain two space-separated integers aa and bb representing a candidate range to possibly leave unpainted.

输出格式

For each of the QQ candidates, output the answer on a new line.

数据范围

Test cases 1-4 satisfy N,Q≤100N,Q\le 100. Test cases 5-7 satisfy N,Q≤5000N,Q\le 5000. Test cases 8-13 satisfy no additional constraints. Problem credits: Andi Qu and Brian Dean

样例

样例 1

8 2
ABBAABCB
3 6
1 4
4
3
In this example, excluding the sub-range corresponding to the desired pattern
$\texttt{BAAB}$ requires four strokes to paint while excluding $\texttt{ABBA}$ 
requires only three.
.... -> AA.. -> ABBB -> ABCB