흙금이네 블로그

아이디어 세그먼트 트리로 특정 범위에서의 최솟값을 저장해두고 찾는 범위에 대해 빠르게 처리한다. 풀이 2357번 최솟값과 최댓값 문제에서 최솟값만 고려하여 풀 수 있다. N보다 큰 2의 거듭제곱 중 가장 작은 값의 두 배 크기로 0으로 채워진 리스트 tree를 만든다. tree의 리프 노드들에 N개의 수를 입력 받고, for문에서 tree의 부모 노드들을 두 자식 노드 중 더 작은 값으로 저장한다. 값이 0인 자식 노드가 포함되어 있는 경우 부모 노드에 0이 아닌 자식 노드의 값을 저장한다. M개의 a, b 쌍을 입력 받아 함수 find를 호출하여 반환된 최솟값을 출력한다. 함수 find에서는 리프 노드에서부터 차례로 부모 노드로 올라가며 최솟값을 res에 저장한다. s%2 == 1 또는 e%2 == 0..

아이디어 세그먼트 트리로 특정 범위에서의 최솟값과 최댓값을 저장해두고 찾는 범위에 대해 빠르게 처리한다. 풀이 N보다 큰 2의 거듭제곱 중 가장 작은 값의 두 배 크기로 0으로 채워진 리스트 min_tree를 만든다. min_tree의 리프 노드들에 N개의 수를 입력 받고, min_tree를 복제하여 max_tree로 저장한다. for문에서 min_tree와 max_tree의 부모 노드들을 각각 두 자식 노드 중 더 작은 값과 더 큰 값으로 저장해 나간다. min_tree에서 값이 0인 자식 노드가 포함되어 있는 경우 부모 노드에 0이 아닌 자식 노드의 값을 저장한다. M개의 a, b 쌍을 입력 받아 함수 find를 호출하여 반환된 최솟값과 최댓값을 언패킹하여 출력한다. 함수 find에서는 리프 노드에서..