백준16977 히스토그램에서 가장 큰 직사각형과 쿼리

작성일 | In

문제 링크

  • http://icpc.me/16977

사용 알고리즘

  • 병렬 이분 탐색

풀이

쿼리 l r w의 답이 x 이상이라는 것은, 높이가 x 이상인 직사각형들만 존재할 때 w개 이상의 직사각형이 연속으로 놓여있다는 것을 의미합니다.
따라서 쿼리가 하나만 존재할 때는 높이가 큰 직사각형부터 보면서, 연속한 직사각형의 개수의 최댓값이 w 이상이 되는 시점을 확인하면 답을 구할 수 있습니다.
이때 연속한 직사각형의 최댓값은 아래와 같은 노드를 가진 세그먼트 트리를 이용하면 구할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node{
  int lmx, rmx; //구간의 가장 왼쪽(오른쪽) 지점을 포함하는 최댓값
  int mx, sum; //구간 전체에서의 최댓값, 현재 구간에 있는 모든 원소의 합
};

Node merge(const Node &a, const Node &b){
  Node ret;
  ret.lmx = max(a.lmx, a.sum + b.lmx);
  ret.rmx = max(a.rmx + b.sum, b.rmx);
  ret.sum = a.sum + b.sum;
  ret.mx = max({ret.lmx, ret.rmx, a.rmx + b.lmx});
  return ret;
}

쿼리가 여러 개 존재하는 경우에는 병렬 이분 탐색(PBS)를 이용해 동일하게 처리해줄 수 있습니다.