조화로운 구간 세기
골드 II의견: 0
수열 \(a_1, a_2, \ldots, a_N\)이 주어진다.
부분 구간 \([l, r]\) (\(1 \le l \le r \le N\))이 조화롭다고 할 때는 그 구간 내 최댓값과 최솟값의 차이가 \(K\) 이하인 경우이다.
즉, \(\max(a_l, \ldots, a_r) - \min(a_l, \ldots, a_r) \le K\)이면 조화로운 구간이다.
조화로운 부분 구간의 총 개수를 구하여라.
- \(1 \le N \le 200\,000\)
- \(0 \le K \le 10^9\)
- \(1 \le a_i \le 10^9\)
첫째 줄에 수열의 길이 \(N\)과 정수 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 수열 \(a_1, a_2, \ldots, a_N\)이 공백으로 구분되어 주어진다.
조화로운 부분 구간의 수를 출력한다.
5 2
1 3 2 5 4
9
\(K = 2\)인 경우, 모든 부분 구간을 검사하면 \([1,1],[2,2],[3,3],[4,4],[5,5]\) (길이 \(1\), \(5\)개), \([1,2],[2,3],[3,4],[4,5]\) (길이 \(2\), 최대-최소 \(\le 2\)인 것), \([2,3]\)은 \(3-2=1\), \([3,4]\)는 \(5-2=3>2\) 제외, \([4,5]\)는 \(5-4=1\). 총 유효 구간의 수는 \(8\)이다.
4 0
5 5 5 5
10
모든 원소가 같으므로 모든 부분 구간의 최대-최소가 \(0\)이다. 부분 구간의 수는 \(\frac{4 \times 5}{2} = 10\)이다.
riseoj 작성
출처 Original
평가 및 의견
조화로운 구간 세기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
조화로운 구간 세기