[BOJ] 13546 수열과 쿼리 4

 

 

https://www.acmicpc.net/problem/13546

13546번: 수열과 쿼리 4

알고리즘: Mo's (+ 평방 분할)

 

시간복잡도: $O((N+M)\sqrt N)$

---

Mo's 알고리즘과 관련된 문제들을 보면,

구간 [l, r]에서 특정 값이 몇 번 등장하는지를 구하는 문제들이 빈번히 등장한다.

push $A_i$: cnt[$A_i$]++

pop  $A_i$: cnt[$A_i$]--

이런 방식으로 말이다.

 

이를 응용하면 문제를 푸는 아이디어는 쉽게 생각해낼 수 있다.

$A_x=A_y$ 일 때, max(|x-y|) 를 구해야한다.

 

1. x-y의 값을 구해야하므로 우리는 index에 대한 정보를 가지고 있어야한다.

2. $A_i$를 push하고 pop를 하는 과정은 구간의 양끝에서 일어난다.

 

따라서, $A_i$를 push하고 pop할 때 $i$(index)를 추가해주거나 빼주면서 값들을 관리해주면 된다.

무턱대고 배열을 100000*100000 을 잡으면 메모리가 터져버릴테니 list를 이용하여 관리해준다.

(deque는 TLE를 받는다고 한다.)

 

 

그럼 끝....?

이면 이 문제가 solved.ac 기준 다이아5 일리가 없다 (...)

Mo's로 구간을 훑을 때, push만 한다면 |x-y|의 최댓값이 보장되지만 pop을 할 때도 있으므로,

$A_i$를 push, pop을 할 때 갱신되는 |x-y|의 값이 최대라는 보장이 없다.

그렇다고 무턱대고 cnt[|x-y|]++, cnt[|x-y|]-- 이런 식으로 |x-y| 값들을 관리해주면

최댓값을 구할 때 $O(N)$이 걸리므로 TLE를 받게 된다. 

 

그래서 |x-y|값도 $\sqrt N$씩 나눠, 버킷으로 관리해줘야한다.

그러면 최댓값을 구하는데 $O(\sqrt N)$이 걸리므로 제한시간 내 해답을 구할 수 있다.

 

---

사실, 평소에 구현하던 mo's 를 조금만 손보면 list와 평방 분할 없이 문제를 해결할 수 있다. 

 

핵심 아이디어는 구간을 따라가면서 원소를 하나씩 pop하는게 아니라 통째로 pop하는 것이다.

 

아래 그림처럼 두 가지의 case를 나눠서 통째로 pop해주면 $O(\sqrt N)$이 보장되면서 쿼리를 해결해줄 수 있다.

(Mo's 알고리즘에서 쿼리를 정렬하는 부분을 잘 살펴보면 왜 그런지 알 수 있을 것이다.)

 

연결된 칸들은 $\sqrt N$씩 나눈 하나의 버킷을 뜻하고, e는 다음 버킷의 시작지점이다. 

l, r 동일 버킷에 존재

 

 

l, r 다른 버킷에 존재

(자세한 설명은 pass)

간단하게 설명하자면 쿼리들이 동일한 버킷에 존재할 때, r은 점차 증가하고 l은 최대 $\sqrt N$씩만 변하므로

$O((M+N)\sqrt N)$만에 모든 쿼리들을 해결할 수 있다.

list의 추가 삭제 연산이나 max 값을 구할 때 평방 분할을 사용할 필요가 없으므로, 1번 풀이보다 속도가 훨씬 빠르다.

 

1번 풀이는 928ms (hilbert curve 이용)

2번 풀이는 320ms 정도 걸렸다. 

 

sol1) Mo's + sqrt decomposition

 

 

sol2) Mo's reset