칠할 시간이 없다

베시는 최근 페인트 세트를 선물 받았고, 목초지 한쪽 끝에 있는 긴 울타리를 칠하고 싶어 한다. 울타리는 연속한 \(N\)개의 1미터 구간(\(1\le N\le 10^5\))으로 이루어져 있다. 베시에게는 26가지 색이 있으며, 어두운 정도가 증가하는 순서로 'A'부터 'Z'까지의 문자로 이름을 붙였다('A'는 매우 밝은 색이고 'Z'는 매우 어둡다). 따라서 베시가 각 울타리 구간에 칠하고 싶은 색은 각 문자가 알파벳인 길이 \(N\)의 문자열로 나타낼 수 있다.

처음에는 모든 울타리 구간이 칠해져 있지 않다. 베시는 한 번의 붓질로 연속한 임의의 구간 범위를 한 가지 색으로 칠할 수 있는데, 단 어두운 색 위에 밝은 색을 칠할 수는 없다(밝은 색 위에 어두운 색만 칠할 수 있다).

예를 들어, 처음에 칠해져 있지 않은 길이 4의 구간은 다음과 같이 칠할 수 있다.

.... -> BBB. -> BBLL -> BQQL

시간이 부족한 베시는 연속한 어떤 범위의 울타리 구간들을 칠하지 않은 채로 남겨 두어야 할지도 모른다고 생각한다! 현재 베시는 \(Q\)개(\(1\le Q\le 10^5\))의 후보 범위를 고려하고 있으며, 각 범위는 칠하지 않고 남겨 둘 구간 범위 \(a \ldots b\)의 양 끝 인덱스를 나타내는 두 정수 \((a,b)\)(\(1 \leq a \leq b \leq N\))로 주어진다.

각 후보 범위에 대해, 범위 안의 모든 울타리 구간은 칠하지 않은 채로 두면서 범위 밖의 모든 울타리 구간을 원하는 색으로 칠하는 데 필요한 최소 붓질 횟수는 얼마인가? 이 과정에서 베시가 실제로 칠을 하는 것은 아니므로, 각 후보 범위에 대한 답은 서로 독립적임에 유의한다.

문제 제공: Andi Qu, Brian Dean

배점

• 테스트 케이스 1-4는 \(N,Q\le 100\)을 만족한다.
• 테스트 케이스 5-7은 \(N,Q\le 5000\)을 만족한다.
• 테스트 케이스 8-13에는 추가 제약이 없다.

문제 제공: Andi Qu, Brian Dean

첫째 줄에 \(N\)과 \(Q\)가 주어진다.

다음 줄에 각 울타리 구간에 칠하고 싶은 색을 나타내는 길이 \(N\)의 문자열이 주어진다.

다음 \(Q\)개의 줄 각각에는 칠하지 않고 남겨 둘 수 있는 후보 범위를 나타내는, 공백으로 구분된 두 정수 \(a\)와 \(b\)가 주어진다.

\(Q\)개의 후보 각각에 대해 답을 한 줄에 하나씩 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > January > Silver