%2022. 1. 9. 00:06에 작성된 글입니다%
23894번: 합성함수와 쿼리 2
함수 $f : \{1, 2, \cdots, N\} → \{1, 2, \cdots, N\}$의 각각의 함숫값 $f(1), f(2), \cdots, f(N)$이 주어진다. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x : $f(1)$의 값을 $x$로 변경한다. 2 m x : $f^m (x
www.acmicpc.net
여행 갔을 때 호텔에서 풀려고 잡았던 문제. 취한 상태였기 때문에 WA만 잔뜩 내고 집에 돌아와서 마저 풀었다.
쿼리 꼴 보면 sparse table 생각이 난다. 2번 쿼리는 어지간하면 \(O(\log m)\)으로 처리 가능하다는 얘기인데, 문제는 1번 쿼리.
1번 쿼리는 \(f(1)\)을 제멋대로 바꿔버리기 때문에 table을 만들어도 \(f(1)\)에 영향을 받는 놈들이 1번 쿼리 들어올 때마다 싸그리 바뀐다.
naive하게 쿼리 들어올때마다 table을 다시 짠다면 \(O(QN)\). 부분 점수나 받고 떨어지기 딱 좋은 시간복잡도가 된다. ㅋㅋ
어쨌든 sparse table를 쓰고는 싶으니까 돌아가서...
'\(f(1)\)에 영향을 받는 놈들' 이걸 살펴보자.
만약 테이블의 어떤 원소가 \(f(1)\)의 값에 영향을 받는다면, 이 녀석은 \(f(1)\)의 값에 \(f\)를 적당한 횟수만큼 합성한 형태임을 알 수 있다. (그렇지 않으면 \(f(1)\)이 변화해도 값이 따라 바뀌는 일이 없다.)
그럼 처음에 sparse table을 만드는데, \(f(1)\)의 값에 대해서 표현되는 원소는 \(f(1)\)에 몇 번 \(f\)를 합성했는지를 값 대신 저장하고, 1번 쿼리가 들어올때마다 저 빈 공간을 다른 곳에다 잘 채워주면 AC.
이상한 데서 고생했는데, 이 문제에서 sparse table를 구현할 때 배열을 [log][N] 구조로 구현하면 쿼리 처리가 느려져서 TLE가 난다. CPU 캐시와 관련된 내용으로 보인다.