BOJ 15055 - Daunting device
문제의 설명은 다음과 같다.
N 길이의 배열
각 배열의 칸은 정수 색을 가진다.
처음에 모든 칸은 같은 색(1)이다.
Q 개의 쿼리
<P X A B>
1. 현재 P색의 개수를 센다. 이 수를 S라 하자.
2. M1 = (A + S^2) mod L
3. M2 = (A + (S + B)^2) mod L
4. [M1, M2] 의 색을 모두 X로 만든다.
쿼리가 끝난 후 가장 많이 나타난 색상을 답하라.
풀이
Square Root Decomposition을 써서 시간복잡도를 증명하고 풀 수 있다.
배열의 길이 $N$ 이고 버킷의 크기를 $B(B\simeq{\sqrt{N}})$ 라고 하자.
어떤 쿼리가 동작해서 어떤 버킷의 구간을 모두 뒤덮는 구간을 색 $X$로 바꿨다면, 해당 버킷의 원소들은 모두 $X$가 되었으므로 버킷의 색을 $X$ 라고 표시해두고 dirty=0 을 설정해줄 수 있다.
dirty 는 해당 버킷이 모두 같은 수를 갖고 있는지 아닌지에 대한 여부이다.
1이면 더러워져서 같은 수를 가지고 있지 않는 것이다.
$L \sim R$ 구간에 쿼리가 들어왔을 때, 구간에 포함되는 버킷들 중 dirty=0 인 것들은 그냥 그 버킷이 갖고 있는 색 그 자체를 이용하고, dirty=1 해당 버킷 안의 색은 하나하나 세준다.
버킷의 개수는 $O(\sqrt{N})$ 개이므로 dirty=0 인 버킷은 빠르게 셀 수 있고, 문제는 dirty=1 이 된 버킷이다.
결론부터 말하자면 이걸 세야하는 순간은 많지 않다.
구간을 업데이트 할 때 최대로 생길 수 있는 dirty=0 인 버킷은 $2$개이다.
어찌되었든 업데이트에 필요한 시간복잡도는 무조건 $O(\sqrt{N})$으로 제한되는 셈이다.
모든 버킷을 하나하나 세줘야 하는 상황($O(N)$ 이 걸리는)을 만들기 위해 대략 $O(\dfrac {\sqrt{N}}2)$ 번의 업데이트 쿼리가 필요하다.
직관적으로 봤을 때 하나하나 세줘야 하는 순간이 어느정도 제한이 된다는 것을 알 수 있다.
좀더 보자면 업데이트 쿼리가 $U$ 개라면, 색의 수를 세는 과정에서 모든 쿼리를 처리해도
만큼밖에 세줄 필요가 없기 때문에 이 또한 $O(Q\sqrt{N})$ 정도로 수렴해서 그냥 제곱근 분할법을 써서 쿼리를 슥슥 구현하면 시간제한내에 통과하게 된다.
구현에서 주의할 점은 어떤 버킷을 dirty=1 로 만들어 줄 때, 일단 그 버킷에 모든 원소들을 버킷의 색상으로 변경해준 후 작업을 해야한다는 것이다.
Comments