문제 BOJ 6549번 풀이 히스토그램 문제에 스택과 세그먼트 트리를 사용한 풀이가 있는데, 세그먼트 트리를 사용하여 풀어보겠습니다. 위와 같은 히스토그램이 있습니다. 아래와 같은 분할 정복을 사용하여 문제를 풀어보겠습니다. * 구간 [left, right]를 정복하고 있을 때, - 해당 구간에서 최소 높이를 h라고 두고, 높이가 h인 직사각형의 인덱스를 i라고 하겠습니다. - (right - left + 1) * h가 답이 될 수 있습니다. - 그리고 구간 [left, i - 1]과 [i + 1, right]에서 다시 분할 정복을 해나가면 됩니다. 테스트케이스를 예시로 설명해보겠습니다. [1, 7]을 정복하고 있을 때 2번째 직사각형의 높이가 1로 가장 작으니(최솟값이 여러개 있으면 아무거나 선택해도 ..

문제 백준 14428번 풀이 전형적인 세그먼트 트리를 구현하는 문제입니다. left ~ right의 대푯값을 left ~ right에서 가장 작은 값의 인덱스로 놓아주고 갱신해주면 됩니다. 소스코드 #include using namespace std; int arr[100001], seg[400001]; int init(int node, int start, int end) { if (start == end) return seg[node] = start; int mid = start + end >> 1; int a = init(node * 2, start, mid), b = init(node * 2 + 1, mid + 1, end); if (arr[a] == arr[b]) return seg[node] =..