BOJ 26615 - 다오의 행사 계획하기

BOJ 26615 - 다오의 행사 계획하기

임의의 두 노드가 항상 겨올가 하나이고 $NM \le 10^5$ 이므로 그냥 격자에서 트리를 만들어서 LCA로 최단 경로를 $O(\log n)$에 구할 수 있게 전처리하자.

그런다음 구간합 배열로 시간 $T$에 대해 imos 법으로 구간합을 쭉 구해주면 정답이다.

오프라인 쿼리 태그도 붙여야할듯