센서 감시
플래티넘 V의견: 0
우주 기지에 \(N\)개의 센서가 일렬로 설치되어 있고, 각 센서는 초기 신호 강도를 가진다.
지휘관은 \(Q\)번의 명령을 내린다.
- 갱신 (타입 1): \(i\)번 센서의 신호 강도를 \(v\)로 바꾼다.
- 구간 감시 (타입 2): \(l\)번부터 \(r\)번 센서 중 신호 강도의 최솟값과, 그 최솟값을 가진 센서의 개수를 구한다.
각 타입 2 명령의 결과를 순서대로 출력하여라.
- \(1 \le N \le 200\,000\)
- \(1 \le M \le Q \le 200\,000\)
- \(1 \le i \le N\), \(\;1 \le l \le r \le N\)
- \(1 \le A_i, v \le 10^9\)
첫째 줄에 센서 수 \(N\), 타입 2 명령의 수 \(M\), 총 명령 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 초기 신호 강도 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 걸쳐 명령이 주어진다.
1 i v— \(i\)번 센서 강도를 \(v\)로 갱신한다.2 l r— 구간 \([l, r]\)의 최솟값과 그 개수를 질의한다.
타입 2 명령마다 한 줄씩, 최솟값과 그 개수를 공백으로 구분해 출력한다.
6 3 4
50 100 30 80 30 10
2 1 6
1 3 20
2 1 6
2 4 6
10 1
10 1
10 1
초기 배열은 \([50, 100, 30, 80, 30, 10]\)이다. 구간 \([1,6]\) 최솟값은 \(10\) (위치 \(6\), 개수 \(1\))이다. 위치 \(3\)을 \(20\)으로 갱신. 구간 \([1,6]\) 최솟값은 여전히 \(10\) (위치 \(6\)). 구간 \([4,6]\) 최솟값은 \(10\) (위치 \(6\), 개수 \(1\))이다.
3 3 6
5 5 5
2 1 3
1 2 3
2 1 3
1 1 3
1 3 3
2 1 3
5 3
3 1
3 3
초기 배열 \([5, 5, 5]\): 구간 \([1,3]\) 최솟값 \(5\), 개수 \(3\). 위치 \(2\)를 \(3\)으로 갱신하면 최솟값 \(3\), 개수 \(1\). 위치 \(1, 3\)도 \(3\)으로 갱신하면 최솟값 \(3\), 개수 \(3\).
riseoj 작성
출처 Original
평가 및 의견
센서 감시
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
센서 감시