BOJ 27173 - 수열과 쿼리 43

 

 

문제 링크

• 27173번: 수열과 쿼리 43 (acmicpc.net)

27173번: 수열과 쿼리 43

 
문제 풀이

 
따끈따끈한 수열과 쿼리 43이 나왔다. 원래는 이 글을 쓸 생각이 없었지만, 지인이 풀이가 보고싶다고 해서, 기왕이면 잘 써볼려고 써보게 되었다.
 
일단, 이 문제를 풀 경지라고 생각하고 정말 대충 풀이를 적으려고 한다.
Segment Tree Beats를 완벽하게 이해하고 있다면, 조금 더 이해가 쉬워 질 것이다.
 
일단 하나하나씩 짚어가면서 풀이하도록 하겠다.

$O(Q \log N)$

우리는 쿼리를 적용시켜 나가면서 $A_i$를 구해야만 한다. 그런데, 2번 쿼리를 보면, $t$ 보다 작은 수가 있으면 쿼리를 무시해야한다.
 
자, 쿼리를 보고 느끼는 건 우리는 구간에 가장 작은 값을 찾는 쿼리를 구현해야 한다는 것이다.
그 쿼리를 구현하면 $A_i$는 구간 $[i, i]$에 작은 수를 찾는 쿼리를 날리면 구할 수 있다.
 
그렇게 우리는 구간에 대해 가장 작은 값을 관리해볼거다.
 
어떤 구간에 대해 가장 작은 값 $X$가 있다고 하자.
이 구간에 2번 쿼리랑 4번 쿼리가 쏟아져 오듯 오는데, 이 쿼리들은 압축 할 수가 없다. 단순히, 2번 쿼리의 합과, 4번 쿼리의 갯수만으로는 $X$값을 정확하게 계산해낼 수 없다. 계산 적용 순서가 $X$값의 결과에 영향을 끼치기 때문이다.
 
4번 쿼리는 어느 구간에 빼는 쿼리로 변환시킬 수 없다, 즉 2번 쿼리와 양립이 불가능하다.. tagCondition을 조정해 더하는 쿼리로 변환 시켜도 시간복잡도가 크게 박살이 난다.. (더하는 쿼리가 아닌, 그냥 특정한 수로 두는 방법은 맨 아래 적혀있다.) 암튼, 나이브로 적용 시켜주어야만 한다.
 
2번과 4번 쿼리의 순서가 중요하므로, 한 구간의 대해 들어온 쿼리의 순서를 저장해보자.
 
이 쿼리들을 그 구간의 가장 작은 값에 적용시키고, 전파 시키면, 쿼리가 들어온 갯수대로 전파하게 된다.
즉 나이브하게 push 당, $O(Q)$ , 결국 시간복잡도는 $O(NQ)$가 될 것이다. 이제 이 쿼리를 최적화 시켜보자.
 
각 쿼리의 특징을 살펴보자.
2번 쿼리는 $A_i := A_i - t$, 3번 쿼리는 등차수열쿼리, 4번 쿼리는 $A_i := \left \lfloor \sqrt{A_i} \right \rfloor$ 이다.
 
2번 쿼리와 4번 쿼리는 단조성을 가지고 있다는 것을 캐치하면 이 문제는 다 풀었다고 볼 수 있다.
$10^{18}$값을 1로 만들기위해서 4번 쿼리는 6번밖에 필요하지 않다.
 
즉, 4번 쿼리가 6번 이상 들어오면, 그 구간의 값은 더 이상 바뀌지 않는다. 물론 그 다음에 2번 쿼리가 들어오면, 1에서 0으로 바뀐다.
 

위의 그림이 어느 적당한 구간에 들어온 쿼리의 번호이고, 관리해보도록 하자.
그럼 2번 쿼리는 합쳐서 저장 할 수 있다. 그럼 무조건 합치면서 관리하자, 어느 적당한 구간에 쿼리가 다음 그림과 같이 2번 쿼리는 합쳐지면서 불연속적으로, 4번은 아무렇게나 저장되어 있을 것이다.

 이렇게 한 구간을 대표하여, 어느곳에 이런 쿼리 순서들을 저장하고 있다고 했을때, 이 길이를 과도하게 들고 있지 않아도 된다는 것을 알 수 있다. 특정 길이 이상 길어진다면, 그 쿼리는 이제 무시해도 된다. 2번 쿼리는 수열에 대해 단조성을 주기 때문에, 수가 변화 할 수 없으면 이제 그 쿼리는 나오지 않는다.
 
이게 길이가 아무리 길어져도 결국에는 4번 쿼리는 6~7번 들어있고, 2번 쿼리가 온다음에, 4번쿼리가 무한히 들어올 수 있다. 그럼 관리할 때, 이 lazy 되어 있는 쿼리 순열을 push할 때, 전파 대상의 쿼리길이를 관리하며 전파하면 된다.
 
최대 쿼리를 적당히 20개까지만 관리해보자.
 
그럼, push 할 때, 현재 노드에 있는 가장 작은 값을 다시 초기화 하는데, $O(1)$, 전파할 때도, $O(1)$이 걸리게 된다.
그렇게 이 방식은 $O(Q \log N)$의 복잡도를 보장한다.
 
3번 쿼리는 워낙 왤논이여서 설명하기가 좀 그렇다. 설명하기엔 한 문제로 까지 있어서, 이 문제를 풀이하는 거랑 풀이량이 거의 비슷해진다. 아래 문제를 풀며, 3번 쿼리 구현을 연습해보는 것을 추천한다.
 
3번 쿼리가 하필 등차수열인 이유는 구간에 수들의 변화를 다이나믹하게 주기위해서 아니였을까 생각해본다.
 
17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 (acmicpc.net)

17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

 

$O(Q\sqrt{N}\log N)$ 틀린 풀이

이 방법은 적혀있는 시간복잡도보다 살짝은 더 빠르다. 내 뇌가 그렇게 말하고 있다. 내가 그렇게 수학을 잘하는 편은 아니여서 계산을 할 수 없다..
 
이 문제를 풀때, 이 방법을 먼저 사용하게 되었다. 이 방법은 정해가 아니지만, 속도가 그렇게 까지 느린편은 아니었고 문제를 풀때 변하는 수열에 대한 관찰력을 키울 수 있어서 이딴 이상하고 신박하고 이해 안되는 이야기도 들어보는 정도는 괜찮을 것 같아 풀이를 해본다.

세그먼트 트리 비츠를 사용하는데 해당 알고리즘을 모르면 시간복잡도 이해가 어려울 것이다. 그냥 최악의 경우에 전체 구간을 $\sqrt{N}$ 개로 분할하고, 그 구간들에 값을 설정한다고 생각하면 이해가 편해질 것 이다.

(시간복잡도에 관한 엄밀한 증명은 생략합니다.)
 
3번 쿼리를 보면, 등차수열의 공차가 1인 것을 볼 수 있는데, 이것은 따지면, 4번쿼리를 처리하기 더 편해진다.

공차가 1인 어떠한 구간에 대하여, 4번 쿼리를 적용 하면, 어느 구간은 값이 같아질 것이다.
 
예를 들어, 1에서 100000까지 순서대로 이루어진 수열에, 4번 쿼리를 한번 적용시키면 316개의 구간으로 나뉘어, 값이 설정된다.

$[1, 2, 3, . . . , 99999, 100000]$ 에 4번 쿼리를 적용시키면, $[1, 1, 1, 2, 2, 2, . . . 316, 316, 316]$ 처럼 연속적인 값들이 들어간다.

$f(x) = \left \lfloor \sqrt{x} \right \rfloor$ 의 개형을 살펴보면, 대략 위의 그림처럼 연속된 x값들의 y값이 같다는 것을 알 수 있다.

x가 커질 수록, 같은 y값을 가지는 x가 엄청 많아 진다는 것을 볼 수 있다.
 
즉, 3번쿼리에 의해 공차가 1인 등차수열로 전환된 하나의 구간에 대해, 4번쿼리는 최대 $\sqrt{N}$개의 구간에 대해 하나의 값으로 변환되는 연속적인 구간을 여러 개 갖는다는 것을 알 수 있다.
 
최댓값이 1이하인 것을 BreakCondition으로 달고 구간의 가장 큰값과 가장 작은값이 4번쿼리에 의해 같아지는 지점을 TagCondition으로 달아놓으면, 등차수열에 의해 비슷한 구간이 많이 최적화 된다. 
 
2번 쿼리가 없어도, 어떤 구간에 대해 4번 쿼리를 거의 나이브로 초기화 하면, 결국 7번도 안되서, 값이 모두 같아져, breakCondition에 다다른다.

즉, 최적화를 보장한다는 것이다.

이 알고리즘에 대하여, 계속 마주칠 수 있는 최악의 경우에 해당 4번 쿼리는 세그먼트 트리의 약 200000개의 노드중에서 5059개의 노드를 탐색한다.
 
$Q$가 500000일 때, 250000개는 등차수열쿼리, 250000개가 4번 쿼리인 경우고, 등차수열 쿼리는 $O(\log N)$으로 처리 할 수 있고, 4번 쿼리는 5059개의 노드를 탐색하므로, 총 1,264,750,000번의 탐색을 하게 된다.