백준 17408 6549

17408 수열과 쿼리24

 

최대값의 위치를 구하는 문제

각 구간의 최대값을 저장한 세그먼트 트리를 만들어서 쿼리를 처리해 주기만 하면 된다

 

업데이트나 트리 값을 바꿀 때 그냥 리턴하지 않고 임시로 값을 저장해 두고

앞쪽 쿼리, 뒷쪽 쿼리 값을 비교해서 최대값을 갱신하는 식으로 구현했다

 

근데.. 아래 코드에서

5

5 4 3 9 5

1

2 3 5

 

하면 14가 나와야 하는데 왜 12가 나오는지 알 수가 없다ㅜ

2 4 5 하면 14가 나오는 거 보면 3-9-5부분이 갱신이 안 된 듯한데 아무리 코드를 봐도 왜 저기만 업데이트가 안 되는지 모르겠다.. 너무 안 풀려서 일단 코드 올리고 패스

 

https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/17408%20%EC%88%98%EC%97%B4%EA%B3%BC%20%EC%BF%BC%EB%A6%AC24.cpp

 

 

6549 히스토그램에서 가장 큰 직사각형

아까 문제가 최대값을 구하는 거라면 이 문제는 최소값을 구하는 문제였다

구하고자 하는 구간에서 만들 수 있는 가장 큰 직사각형의 높이는 바로 높이가 가장 작은 막대가 된다

그러므로 아까와 반대로 최소값을 저장하는 세그먼트 트리를 만들고 해당 높이를 가지고 직사각형 넓이를 출력하면 되었다