레이팅 미적용베시는 최근 그림 도구 세트를 받았고, 목초지 한쪽 끝에 있는 긴 울타리를 칠하고 싶어 한다. 울타리는 연속된 1미터 구간 \(N\)개(\(1\le N\le 2\cdot 10^5\))로 이루어져 있다. 베시는 서로 다른 \(N\)가지 색을 사용할 수 있으며, 어두운 순서가 증가하도록 \(1\)부터 \(N\)까지 번호를 붙였다 (\(1\)은 매우 밝은 색이고 \(N\)은 매우 어두운 색이다). 따라서 베시는 각 울타리 구간에 칠하고 싶은 색을 \(N\)개의 정수 배열로 표현할 수 있다.
처음에는 모든 울타리 구간이 칠해져 있지 않다. 베시는 한 번의 붓질로 연속된 구간 범위를 하나의 색으로 칠할 수 있는데, 더 어두운 색 위에 더 밝은 색을 칠할 수는 없다 (밝은 색 위에 어두운 색만 칠할 수 있다).
예를 들어, 처음에 칠해져 있지 않은 길이 4의 구간은 다음과 같이 칠할 수 있다:
0000 -> 1110 -> 1122 -> 1332
안타깝게도 베시는 페인트가 마르는 것을 지켜보며 시간을 낭비할 여유가 없다. 그래서 베시는 일부 울타리 구간을 칠하지 않고 남겨 두어야 할지도 모른다고 생각한다! 현재 베시는 \(Q\)개(\(1\le Q\le 2\cdot 10^5\))의 후보 범위를 고려하고 있으며, 각 범위는 칠할 구간 범위 \(a \ldots b\)의 양 끝 인덱스를 나타내는 두 정수 \((a,b)\) (\(1 \leq a \leq b \leq N\))로 표현된다.
각 후보 범위에 대해, 범위 밖의 모든 울타리 구간은 칠하지 않은 채로 두면서 범위 안의 모든 울타리 구간을 원하는 색으로 칠하는 데 필요한 붓질의 최소 횟수는 얼마인가? 이 과정에서 베시가 실제로 칠을 하는 것은 아니므로, 각 후보 범위에 대한 답은 서로 독립적이다.
문제 제공: Andi Qu, Brian Dean, Benjamin Qi
채점 방식
- 테스트 케이스 1-2는 \(N,Q\le 100\)을 만족한다.
- 테스트 케이스 3-5는 \(N,Q\le 5000\)을 만족한다.
- 테스트 케이스 6-10에서는 입력 배열에 \(10\)보다 큰 정수가 없다.
- 테스트 케이스 11-20은 추가 제약이 없다.
문제 제공: Andi Qu, Brian Dean, Benjamin Qi
첫째 줄에 \(N\)과 \(Q\)가 주어진다.
다음 줄에 각 울타리 구간에 칠하고 싶은 색을 나타내는 \(N\)개의 정수 배열이 주어진다.
다음 \(Q\)개의 줄에는 각각 칠할 후보 범위를 나타내는, 공백으로 구분된 두 정수 \(a\)와 \(b\)가 주어진다.
\(Q\)개의 후보 각각에 대해 답을 한 줄에 하나씩 출력한다.
8 4
1 2 2 1 1 2 3 2
4 6
3 6
1 6
5 82
3
3
3In this example, the sub-range corresponding to the desired pattern
1 1 2
requires two strokes to paint. The sub-range corresponding to the desired
pattern
2 1 1 2
requires three strokes to paint. The sub-range corresponding to the desired
pattern
1 2 2 1 1 2
requires three strokes to paint. The sub-range corresponding to the desired
pattern
1 2 3 2
requires three strokes to paint.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > February > Platinum