BOJ 26615 - 다오의 행사 계획하기
임의의 두 노드가 항상 겨올가 하나이고 $NM \le 10^5$ 이므로 그냥 격자에서 트리를 만들어서 LCA로 최단 경로를 $O(\log n)$에 구할 수 있게 전처리하자.
그런다음 구간합 배열로 시간 $T$에 대해 imos 법으로 구간합을 쭉 구해주면 정답이다.
오프라인 쿼리 태그도 붙여야할듯
임의의 두 노드가 항상 겨올가 하나이고 $NM \le 10^5$ 이므로 그냥 격자에서 트리를 만들어서 LCA로 최단 경로를 $O(\log n)$에 구할 수 있게 전처리하자.
그런다음 구간합 배열로 시간 $T$에 대해 imos 법으로 구간합을 쭉 구해주면 정답이다.
오프라인 쿼리 태그도 붙여야할듯
Comments