10. 14

• 오랜 숙원 중 하나였던, CERC14의 <Pork Barrel>을 무려 14108ms의 수행시간으로(..) AC를 받았다. 기본 원리는 APIO13의 <Toll>과 유사하게, 동적 MST에 관한 것이다. 엣지를 추가하다가 cycle이 발견되면, 해당 cycle의 최대요소를 제외한다는 것이 idea이다. 이문제에서는 이런 서로 대체관계에 있는 엣지들의 pair를 묶어버리고, 여기에서 range sum query를 수행해야 했다. 즉 range에 두 엣지가 모두 들어갈 수 있으면, 작은 weight의 엣지로 대체하는 방식이다. 이는 배열을 저장하는 segment tree로 \( O( \lg^2{N} ) \)의 단위쿼리 수행시간을 맞출 수 있다.
• 해당 코드는 내 것이 아니고 solution에 나온 것인데, vft는 vector로 된 fenwick tree를 말하는 것 같다(..) struct를 짜면서 vector를 상속해버리는 것도 괜찮은 방법인 것 같다. 해당 코드가 STL와 C++11을 정말 능숙하게 다뤄서, 배우는 게 많았다.
• segment tree도 충분히 복잡한데, 여기에 persistent가 붙으면 복잡도가 제곱이 된다-_- 일단 어떤 방식으로, 무엇을 저장할지조차 감이 안잡히니까 update/query연산의 정의조차 정하기가 힘들어진다.. 여기서는 edge를 기준으로 segment tree를 만드는데, 각 range branch마다 '범위 최소가 i가 나왔을 때의 구간합 x'를 구하기 위해 이를 영역으로 나타냈다. 그래서 완전히 포함되는 range의 경우 binary search를 통해 합을 더하는 것..
• 자료구조 문제는 특히, 해법이 대충 나온 후에도 구현에 정말 망설여지는 부분이 있다. 자료구조에서 발생한 조그만 버그는 상상초월로 디버깅이 어렵다는 걸 알기도 하고.. 애초에 머릿속에 확실하게 떠오를 만큼 이해하지 못했기 때문이기도 함.