Sign on Fence (CF 276E)

http://www.codeforces.com/contest/484/problem/E

질의를 볼 때 모든 길이 w의 subsegment를 다 볼거라는 생각으로는 진전이 없다. 대신, 답을 정해놓는 식의 binary search를 유용하게 쓸 수 있다.

binary search로 접근해보자. 질의의 답이 H[i]라고 가정했을 때, 구간 [l, r] 내에서 주어진 조건을 만족하려면, H[i] 이상의 원소들로만 이루어진 연속 최대 구간의 길이가 W 이상이어야 한다.

즉 문제는 구간 [l, r] 내에서 H[i] 이상의 원소들로만 이루어진 연속 최대 구간의 길이를 구하는 것으로 정리되었다. 크게 두가지 방법이 있다.

* 1. Persistent Segment Tree

기본적으로 구간 [l, r] 내에서 연속 최대 구간의 길이를 구하는 가장 좋은 방법은 세그먼트 트리이다. {왼쪽에서 시작하는 최대 길이 / 오른쪽에서 시작하는 최대 길이 / 그냥 최대 길이 / 구간의 크기} 를 저장하면, O(lgN)에 질의를 해결할 수 있다.

문제는 H[i] 이상의 원소들로만 이루어져있어야 한다는 점인데, 이는 Persistent Segment Tree를 만들어주면 된다. 초기 시작 시, H[i] 증가 -> 감소 순으로 세그먼트 트리에 노드를 넣어주면 H[i]가 없는 풀이와 전혀 차이 없이 해결할 수 있다. 질의당 트리 O(lgN) * 이진탐색 O(lgN) = O(lg^2N).

http://www.codeforces.com/contest/484/submission/16654359

* 2. Parallel Binary Search

좋은 이름이 없어서 그냥 코포 댓창에서 누가 쓴 이름을 그대로 가져온다.

PST를 안쓰고 풀려면 오프라인 방법의 이점을 사용해야 하는데, 이진 탐색이 필요하기 때문에 쉽지 않다. 하지만, Q개의 쿼리에 대해서 이진 탐색을 한번에 하면..? 초기 쿼리들의 답의 범위를 (S[i], E[i]) 라고 하고, M[i] = (S[i] + E[i]) / 2로 쓴다.

* 각각의 쿼리는 [l, r] 내에서 H[M[i]] 이상의 원소들로만 이루어진 연속 최대 구간의 길이를 구하는 것이다.

* 이는 연속 최대구간 세그트리를 가지고 plane sweeping 비슷하게 구하면 O(NlgN)이다.

* 만약에 이 때 연속 최대 구간의 길이가 충분히 크다면, 해당 쿼리에 대해서는 범위를 위로 좁혀주고, 아닌 쿼리에 대해서는 범위를 아래로 좁혀준다.

이러한 식으로 하면 plane sweeping O(lgN) 번에 문제를 해결할 수 있다.

http://www.codeforces.com/contest/484/submission/16655268

두 방법 모두 코드 길이나 코딩 난이도는 비슷하다 (1번이 조금 더 쉽다). 글을 쓴 이유는 2번 풀이 때문인데 여기 저기서 강력하게 쓸 수 있는 테크닉인거 같아서 소개해보고자 썼다.