Codeforces Educational Codeforces Round 13 - F. Lena and Queries

문제 링크 : http://codeforces.com/contest/678/problem/F

세 가지 쿼리가 주어진다.

1. 기울기가 a이고 절편이 b인 선분 삽입

2. 이전에 삽입되었던 i번째 선분 삭제

3. 현재 선분 집합에서 특정 x 좌표에 대한 최댓값 출력

풀이 1. - Time Limit Exceeded

쿼리를 루트개씩 묶음으로 나눔. 반평면 땅따먹기 문제에서의 부저장소-저장소 방법으로 각 묶음마다 해결함. 3번 쿼리에 대해서는 이전의 묶음들 + 현재 채우고 있는 묶음에서 답을 찾음.

부저장소-저장소 컨벡스헐 트릭 방법은 이 링크에 설명되어 있다.

http://codeforces.com/contest/678/submission/18520250

풀이 2. - Accepted

오프라인으로 문제를 해결함. 쿼리를 입력 다 받아놓고 선분은 선분끼리, 특정 x좌표들은 그 좌표들끼리 모음. 선분들은기울기, 절편과 Time interval도 가짐. 몇 번째 쿼리부터 몇 번째 쿼리까지 살아있다는 정보. 이건 1번 쿼리와 2번 쿼리로 구할 수 있음.

선분들은 기울기 순으로 정렬하고, 좌표들은 크기 오름차순으로 정렬함.

이제 전체 Time interval을 루트 크기씩 묶음으로 볼 거임. 지금 관심있는 구간을 [lt, rt]라고 하겠음. 모든 선분들에 대해 3가지로 분류를 함.

1) [lt, rt]를 완전히 커버하는 Time interval을 가진 선분 : 컨벡스헐 트릭 구조에 삽입

2) [lt, rt]에 걸치는 Time interval을 가진 선분 : 별도로 모음

3) 그 외의 선분 : 버림

이제 질문들을 모두 볼 거임. 만약 좌표의 쿼리 index가 [lt, rt]에 포함된다면 1)에서의 컨벡스헐 트릭에서 답 갱신할 수 있음. 그리고 2)들에 대해서 답을 다 갱신함.

1)에 대한 계산은 Time interval이 정해졌을 때에, 좌표 순으로 정렬해놓았기 때문에 모든 질문에 대해서 선형에 될거고, 2)에 대한 계산은 걸치는 선분이 최대 2루트개이기 때문에 선형에 됨.(time interval 안에 있는 좌표가 루트개 * 걸치는 선분이 루트개 = 선형)

따라서 전체적인 시간복잡도는 이 됨.

http://codeforces.com/contest/678/submission/18533472

풀이 3. 

컨벡스헐을 세그먼트 트리로 구성.