[IOI2013 Day2] Game 해법

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day2/game/game - KOR (ko).pdf
영문: http://www.ioi2013.org/wp-content/uploads/tasks/day2/game/game.pdf

이 문제는 전형적인 2차원 Segment Tree 문제다.

흔히들 알고 있는 Indexed tree로 이 문제를 풀 경우 $R$ 값이 매우 커 배열을 잡을 수 없지만, top-down 방식을 이용하는 segment tree를 이용하면 된다. 이 문제는 online 방식으로 이후 데이터가 어떻게 들어올지 전혀 예측하지 못한 채로 함수를 코딩해야 되기 때문에 re-indexing 혹은 re-numbering 을 할 수 없다. 불가피하게 segment tree를 사용해야한다.
(필자도 처음 Indexed tree라 배웠던 자료구조가 실은 다른 이름이 있다는데 충격을 받았었지만, 꾸준히 Indexed tree라고 부른다.)

우선 이해를 돕기 위해 1차원일 경우에 대해 얘기해보자. 매우 간단히도, Segment Tree를 만들고 값으로는 두 자식의 최대공약수를 가지고 있으면 된다. $R$ 값이 10억으로 매우 크지만 앞서 말했다시피 top-down 방식을 이용하면 최적의 메모리로 해결가능하다.

Segment tree, Indexed tree, Range tree 등등의 자료구조가 익숙하지 않은 사람들은 이를 2차원에 적용하기 까다로울 것이다. 하지만 새로운 원리나 개념이 등장하지는 않으므로 겁먹지 않아도 된다. 행의 Segment tree의 각 노드에 열의 Segment tree가 있다고 보면 된다.

하지만, 단순한 Segment Tree 구축으로는 80점을 받는다. 이유인즉슨, 아슬아슬한 차이로 메모리제한에 걸린다. 이를 100점으로 올리기 위해 여러 방법이 존재할 것이라고 생각한다. 필자는 조금의 트릭으로 Segment Tree에서 무의미한 노드들을 줄여 메모리를 확보했다.

그 트릭을 간단히 소개하겠다. 

이 문제에서 update 되는 것은 구간에 값을 입력하는 것이 아닌, 노드에 값을 입력하는 것 뿐이다. 그러면 Segment tree에서 노드가 추가될 때 leaf 노드를 추가하게 되고 새로운 leaf 노드가 추가되면 위에 root 까지 연결하는 branch 노드들이 생긴다. 이 branch 노드들을 무의미하다고 볼 수 있기 때문에 유동적으로 필요에 의해 branch 노드들을 만들어 주면 메모리를 아낄 수 있다. 다만, 이 방법은 행의 Segment tree에서는 사용할 수 없다. 행의 Segment tree의 각 노드들은 열의 Segment tree 들의 정보를 가지고 있는데 이를 유동적으로 만들어 줄 수 없기 때문이다. 따라서 열의 Segment tree에서만 branch 노드들을 유동적으로 만들어주면 메모리를 아껴 100점을 받을 수 있다.

코드: http://ideone.com/OoUM6r