이동식 저장소

17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 �� www.acmicpc.net 쿼리 문제의 특징은 쿼리가 매우 많다는 점이다. 보통은 쿼리를 선형 시간보다 더 빠르게, 즉 로그 시간이나 상수 시간에 처리해야 한다. 이 문제 역시 쿼리의 수 Q가 20만, 합성 횟수 N이 50만으로 O(QN) 시간에 해결할 수 없다. 내가 지금까지 풀었던 쿼리 문제는 보통 쿼리를 로그 시간에 처리했다. 이번에도 로그 시..