IOI 2013 Game 풀이 (정해와 다른 풀이)

문제내용 : https://www.acmicpc.net/problem/23839

이 문제의 80점짜리 서브태스크까지는 전형적인 2D SegmentTree를 이용하여 풀이할 수 있다. 딱히 소개할 가치가 있지도 않고 쉽게 알아볼 수 있으므로 그 내용은 생략한다. 하지만 100점은 받지 못하는데, 메모리 초과가 나기 때문이다. 정해는 먼가 독특한 테크닉을 사용하여 메모리를 줄이는 것 같은데, 원래 (왼쪽 자식노드,오른쪽 자식노드,값)에 각각 4바이트, 4바이트, 8바이트를 사용하여 한 노드에 16바이트의 메모리가 사용되는데 이것을 12바이트로 줄여서 문제를 풀 수 있는 풀이가 있어서 소개하려고 한다.

그 방법은 매우 간단하다. 다이나믹 세그먼트트리에서 노드가 생성되는 방식을 생각해보자. 어떤 노드가 생성되고나면, 그 다음 순서에는 그 노드의 자식 노드 중 하나가 생성된다. 그러므로 노드가 생성되는 순서대로 인덱스를 매긴다면, 그 노드의 다음 인덱스는 무조건 왼쪽 자식노드 또는 오른쪽 자식노드이다. 그러므로 노드의 자식들을 저장하는 메모리에서 1비트를 사용하여, 그 노드의 다음 인덱스에 있는 그 노드의 자식노드가 왼쪽 노드인지 오른쪽 노드인지를 저장한다. 그 노드가 리프 노드인 경우는 따로 숫자를 매겨두면 된다. 그리고 남는 메모리에 그 노드의 다음 인덱스에 있는 노드가 아닌, 나머지 노드의 인덱스를 저장하면 된다. 그렇게 하면 자식 노드 두 개의 위치를 저장하는데에 4바이트밖에 들지 않아, 노드 하나에 총 12바이트가 들어서 메모리를 커팅할 수 있고, 이러면 아슬아슬하게 메모리제한에 들어와 문제가 풀린다.