6153 : 세그먼트 트리 — 구간 최대
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N개의 수로 이루어진 수열에서 값을 변경하는 연산과 구간 최댓값을 구하는 연산을 빠르게 수행하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 수열의 크기 N과 쿼리의 개수 Q (1 ≤ N, Q ≤ 100,000)가 공백으로 구분되어 주어집니다.
둘째 줄에 N개의 수가 공백으로 구분되어 주어집니다.
셋째 줄부터 Q개의 줄에 걸쳐 쿼리 정보가 주어집니다.
-
-
둘째 줄에 N개의 수가 공백으로 구분되어 주어집니다.
셋째 줄부터 Q개의 줄에 걸쳐 쿼리 정보가 주어집니다.
-
1 i val: i번째 수를 val로 변경합니다.-
2 l r: l번째 수부터 r번째 수까지의 최댓값을 구합니다.출력 설명
2번 쿼리가 주어질 때마다 해당하는 구간 최댓값을 한 줄씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
1 2 3 4 5
2 1 3
1 3 6
2 1 3
2 2 5
2 3 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
3
5
3