BOJ 22876 츠바메가에시

 

문제 링크 : https://www.acmicpc.net/problem/22876

22876번: 츠바메가에시

 

어릴 적 게임에서 보았던 이름을 보게 되어 반가운 마음으로 문제를 읽었는데...

후회했다. 

 

매 번 세그먼트 트리를 설명할 수 없으니 세그먼트 트리에 대한 설명은 여기 를 참조하자.

 

일단 예외적인 경우부터,

행이나 열이 3 개 이하이면 모두 제거할 수 있으니 답은 전체 제비의 합이다.

 

위의 경우가 아니라면,

1 행을 제거하면 모든 열(수십만 개일 수 있는)에 합에 영향을 미치고(update),

변경된 열이 합들 중에서 큰 값 두개를 찾아야(query) 한다.

 

문제가 세그먼트 트리 카테고리에 있지 않더라도 다른 방법은 생각나지 않을 듯하다.

1. coor_compress 함수가 하는 일을 이해하면 나머지는 보이는 것만큼 복잡하지 않다.

2. xSum 은 x 좌표에 대응되는 열의 모든 원소의 합들을 보관하고 ySum 은 y 좌표에 대해 같은 역할.

3. 작명 수준을 알려주는 xyrr 은 같은 x 좌표에 대응되는 점들의 y 좌표들과 그에 따른 값을 저장하는 이중 배열 

4. segment tree 는 으뜸, 버금 값을 저장하는 구조