좌표압축1 백준 14413 자바 - Poklon (BOJ 14413 JAVA) 문제 : boj14413 1. update가 없는 쿼리 문제로, 오프라인 쿼리로 처리해도 된다. 또한 각 쿼리마다 범위가 계속 변경되는 와중에 원하는 답을 구하는 쿼리 문제이다. 따라서 mo's algorithm을 사용할 경우 효율적으로 풀 수 있다. 모스 알고리즘은 쿼리의 수가 n이고 각 쿼리 qi = (a, b)라 할 때(문제에선 l, r이었음. l이 헷갈려서 a, b로 변경하여 설명함), 모든 쿼리를 (a/sqrt(n), b) 순서로 정렬하게 된다(a/sqrt(n)은 소수점 버리고 정수로). 이 경우 각 쿼리를 정렬 후 수행 시 모든 경우에 대해 a와 b의 변화량이 최대 N*sqrt(N) 정도로 고정되고, 효율적으로 직전에 구해둔 쿼리의 데이터 중 중복되는 부분을 재사용할 수 있다. 예를들어 q1=.. 2021. 12. 11. 이전 1 다음
