백준 2912 자바 - 백설공주와 난쟁이 (BOJ 2912 JAVA)
문제 : https://www.acmicpc.net/problem/2912 1. 기본적인 아이디어는 각 쿼리의 [a, b] 구간에 대해 매번 [a, b] 전체를 확인하지 않고, 이전에 확인했던 구간과 겹치는 구간은 제외하고 확인하는 것이다. 예를들어 이전에 확인했던 구간이 [1, 100]이고 이번에 확인할 구간이 [4, 95]라고 해보자. 이 때, [1, 100] 구간을 전부 확인하면 100번 + [4, 95] 구간을 전부 확인하면 92번 봐야 한다. 그럼 192번 동작해야 한다. 하지만 [1, 100] 구간의 결과에서 [1, 3] 구간을 빼고, [96, 100] 구간을 빼면 [4, 95] 구간 전체를 본 것과 동일한 결과를 얻을 수 있다. 이 경우 108번만 동작하면 된다. 2. update가 없는 쿼..
2021. 11. 20.
