https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 세그먼트 트리 응용 문제 세그먼트 트리를 이용해 구간 합을 미리 구하거나 최솟값을 적는 등으로 활용이 가능했으나, 해당 문제에서는 tree[node]에 가장 작은 값의 인덱스를 집어 넣어 문제를 해결할 수 있다. 원리는 아래와 같다. 예제로 살펴보면, 먼저 가장 작은 값의 인덱스인 1을 기준으로 히스토그램의 넓이를 구한다. 이후 1의 왼쪽과 오른쪽을 다시 기준으로 ..
