문제 링크
- http://icpc.me/8876
문제 출처
- 2013 IOI Day2 3번
사용 알고리즘
- 2D Segment Tree
시간복잡도
- $O(log R log C)$
풀이
단순한 2D Segment Tree 문제입니다. 메모리 제한이 작은 것만 빼면…
100점을 받기 위해서는 이상한 테크닉을 써야 합니다.
각 쿼리마다 필요한 노드만 생성해서 각 쿼리마다 $O(log N)$개의 노드만 생성하는 Dynamic Segment Tree가 널리 알려져있습니다.
행에 대한 세그먼트 트리는 이 방법으로 만들어주면 각 쿼리마다 최대 $O(log R)$개의 열에 대한 세그먼트 트리가 생성됩니다.
이제 열에 대한 세그먼트 트리만 처리하면 되는데, 위에서 썼던 Dynamic Segment Tree를 그대로 사용하면 80점정도를 받게 됩니다.
기존에 사용했던 Dynamic Segment Tree를 떠올려보면, 리프노드까지 모두 생성을 하기 때문에 $O(log N)$개의 노드를 생성했습니다.
어떤 구간 $[S, E]$에 리프 노드가 단 하나만 존재한다면, 굳이 $O(log N)$개의 노드를 생성할 필요가 없습니다.
이런 아이디어를 적용하면 열에 대한 세그먼트 트리는 각 쿼리마다 $O(1)$개의 노드만 생성하게 되고, 100점을 받을 수 있습니다.