스카이라인의 두 번째 봉우리
플래티넘 IV의견: 0
어느 신도시의 큰길을 따라 \(N\)개의 건물이 일렬로 늘어서 있다. 왼쪽부터 \(i\)번째 건물의 높이는 \(H_i\)이다.
도시 관리 시스템은 다음 두 종류의 작업을 입력으로 주어진 순서대로 처리한다.
- 타입 \(1\) (
1 p x꼴): \(p\)번째 건물을 허물고 그 자리에 높이가 \(x\)인 새 건물을 세운다. 즉 \(H_p\)의 값을 \(x\)로 바꾼다. - 타입 \(2\) (
2 l r꼴): 왼쪽에서 \(l\)번째부터 \(r\)번째까지의 건물 \(H_l, H_{l+1}, \dots, H_r\)을 살펴본다. 이 구간에 나타나는 서로 다른 높이들 중 두 번째로 큰 높이를 그 구간의 준봉우리 높이 라고 하자. 구간 안에서 높이가 준봉우리 높이와 정확히 같은 건물이 몇 개인지 출력한다.
조금 더 엄밀하게 말하면, \(l \le i \le r\) 이면서 \(H_l, H_{l+1}, \dots, H_r\) 중에서 \(H_i\)보다 큰 서로 다른 높이가 정확히 한 종류뿐인 \(i\)의 개수를 출력하면 된다.
만약 구간 \(H_l, \dots, H_r\)에 서로 다른 높이가 한 종류밖에 없어 준봉우리 높이 가 존재하지 않는다면 \(0\)을 출력한다.
- \(1 \le N, Q \le 2 \times 10^5\)
- \(1 \le H_i \le 10^9\)
- 타입 \(1\) 작업에서 \(1 \le p \le N\)이다.
- 타입 \(1\) 작업에서 \(1 \le x \le 10^9\)이다.
- 타입 \(2\) 작업에서 \(1 \le l \le r \le N\)이다.
- 타입 \(2\) 작업은 적어도 하나 존재한다.
- 입력으로 주어지는 모든 값은 정수이다.
첫째 줄에 두 정수 \(N\)과 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 건물들의 높이 \(H_1, H_2, \dots, H_N\)이 공백으로 구분되어 주어진다.
이후 \(Q\)개의 줄에 각 작업이 주어진다. 각 작업은 다음 두 형식 중 하나이다.
1 p x2 l r
타입 \(2\) 작업의 개수를 \(q\)라고 할 때, 총 \(q\)개의 줄을 출력한다. \(i\)번째 줄에는 \(i\)번째 타입 \(2\) 작업에 대한 답을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 20점 | \(N, Q \le 2000\) |
Subtask 2 | 30점 | 모든 작업이 타입 \(2\)이다. (즉, 타입 \(1\) 작업이 주어지지 않는다.) |
Subtask 3 | 50점 | 추가 제한이 없다. |
6 5
7 7 2 5 5 9
2 1 4
2 3 6
1 2 9
2 1 6
2 4 41
2
1
0처음 높이는 \(H = (7, 7, 2, 5, 5, 9)\)이다.
- 첫 작업
2 1 4: 구간 \((7, 7, 2, 5)\)의 서로 다른 높이는 \(\{2, 5, 7\}\)이고, 가장 큰 높이는 \(7\), 준봉우리 높이는 \(5\)이다. 구간 안에 높이가 \(5\)인 건물은 하나뿐이므로 \(1\). - 둘째 작업
2 3 6: 구간 \((2, 5, 5, 9)\)의 준봉우리 높이는 \(5\)이고, 구간 안에 \(5\)가 둘 있으므로 \(2\). - 셋째 작업
1 2 9: 둘째 건물의 높이가 \(9\)로 바뀌어 \(H = (7, 9, 2, 5, 5, 9)\)가 된다. - 넷째 작업
2 1 6: 구간 \((7, 9, 2, 5, 5, 9)\)의 가장 큰 높이는 \(9\), 준봉우리 높이는 \(7\)이다. \(7\)인 건물은 하나뿐이므로 \(1\). - 다섯째 작업
2 4 4: 구간 \((5)\)에는 서로 다른 높이가 하나뿐이라 준봉우리 높이가 없으므로 \(0\).
1 1
1000000
2 1 10건물이 하나뿐이라 어떤 구간을 보아도 서로 다른 높이가 하나뿐이다. 준봉우리 높이가 존재하지 않으므로 \(0\).
8 6
4 4 6 6 6 1 3 4
2 1 5
2 6 8
1 7 6
2 5 8
2 1 8
2 3 32
1
1
3
0처음 높이는 \(H = (4, 4, 6, 6, 6, 1, 3, 4)\)이다.
2 1 5: 구간 \((4, 4, 6, 6, 6)\)의 준봉우리 높이는 \(4\)이고, \(4\)가 둘이므로 \(2\).2 6 8: 구간 \((1, 3, 4)\)의 준봉우리 높이는 \(3\)이고, \(3\)이 하나이므로 \(1\).1 7 6: \(H = (4, 4, 6, 6, 6, 1, 6, 4)\)가 된다.2 5 8: 구간 \((6, 1, 6, 4)\)의 가장 큰 높이는 \(6\), 준봉우리 높이는 \(4\)이고 \(4\)가 하나이므로 \(1\).2 1 8: 구간 전체 \((4, 4, 6, 6, 6, 1, 6, 4)\)의 준봉우리 높이는 \(4\)이고, \(4\)가 셋이므로 \(3\).2 3 3: 구간 \((6)\)에는 준봉우리 높이가 없으므로 \(0\).
rip 작성
출처 지정되지 않음
평가 및 의견
스카이라인의 두 번째 봉우리
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
스카이라인의 두 번째 봉우리