Mo's Algorithm (백준 13547)

오프라인쿼리

일반적으로 우리는

쿼리를 받음 -> 계산함 을 반복했는데,

오프라인쿼리는 쿼리를 다 받고, 효율적으로 처리할 수 있게 정렬한 후 쿼리를 순회하며 원래 순서에 맞게 정답을 채워주는 형식의 문제이다.

이런것은 효율적으로 처리할 수 있게 쿼리를 정리했을 때, 이전에 사용한 정보가 이번쿼리를 계산할때 사용될 수 있음 된다.

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

2463번: 비용

이렇게 쿼리를 거꾸로 보면서(들어온 시간에 대해 거꾸로 정렬한다.) 처리하는 문제가 몇개 있는데 이것도 오프라인 쿼리인 것이다.

 

아이디어

길이 N인 배열 A가 있을 때

0 <= i <= j < N에 대해

i부터 j까지의 합을 구하는 문제가 있다.

물론 가장 쉽고 효율적인건 imos고

segment tree도 있겠지만, 우선 가장 비효율적인 것을 생각해보자.

우리는 그러면 쿼리를 받을 때 마다

def compute(i,j):
	result = 0
	for x in range(i,j+1):
    	result += arr[x]
    return result

이 함수를 호출시키면 된다.

만약 첫번째 쿼리가 i=3,j=5이고 두번쨰 쿼리가 i=1 j=10이라해보자.

3~5는 쌩으로 구한다 했을때, 1~10도 썡으로 구할 필요가 있을까?

우리가 3~5의 값을 알면 1~10은 1~2의 값과 6~10의 값만 알면 된다.

또 예를 들어서 3~8을 알고있다하면 5~7은 3~8에서 3~4의 값과 8~8의 값을 빼주면 구할 수 있다.

즉 이전 쿼리의 정보를 알면 좀 더 빠르게 구할 수 있단 것이다.

단 아무것도 정렬을 안한다면 위 풀이도 쿼리당 O(N)일 것이다.

Mo's는 쿼리를 쿼리를 어떻게 효율적으로 정렬하는가에 대한 알고리즘이다.

 

Mo's

우선 우린 쿼리를 시작점에 대해 정렬하고 시작점이 같다면 끝점이 빠른순으로 정렬해보는걸 생각할 수 있을 것이다.

단 그러면 i,N-1쿼리를 계산하고 i+1,i+1쿼리를 계산한다고하면 비효율 적임을 알 수 있다.

만약 시작점을 어떠한 그룹에 묶고 그 그룹순으로 정렬 후 그 그룹에 속한 것중 끝점을 빠른 순으로 정렬하면 어떻게 될까.

그럼 우린 쿼리의 개수와 독립적으로

1. 각 그룹내에서 i가 이동함과 동시에 j가 N-1까지 이동한다.

2. 다음그룹으로 간다.

이런 작업을 맨 마지막 쿼리까지 반복하게 된다.

여기서 Mo's는 그룹의 기준을 sqrt(N)으로 잡는다.

sqrt(N)크기의 그룹이 sqrt(N)개 생길 것이다.

즉 쿼리는

1. int(i//sqrt(N))이 적은 것 기준으로 정렬한다.

2. 만약 int(i//sqrt(N))이 같다면 j가 작은 것 기준으로 정렬한다.

query = []
for i in range(M):
    a, b = map(int, input().split())
    query.append((a, b, i)) # 쿼리 순서를 섞을 것이므로 원래 순서도 담아둔다.
query.sort(key=lambda x: (x[0] // (N ** 0.5), x[1]))

우리는 알고리즘을 위해 다음이 필요하다.

A. x번째 쿼리 I_x와 J_x에서  그 다음쿼리 I_x+1와 J_x+1로 이동하기 위한 두개의 포인터 start, end

B. 포인터를 이동할 때 마다 쿼리의 결과를 구하는 데 필요한 변수

C. 포인터를 이동할 때 마다 변하는 상태를 기록하기 위한 배열

우리는 A,B,C를 이용해 함수도 작성해야한다.

1. I_x == I_x+1

이건 처리할 필요 없다.

2. I_x < I_x+1

start를 I_x에서 I_x+1까지 이동해야한다.

여기서 I_x~I_x+1-1 까지의 데이터를 제외시켜줘야한다.

3. I_x > I_x+1

start를 I_x에서 I_x+1까지 이동해야한다.

여기서 I_x+1~I_x+1 까지의 데이터를 추가시켜줘야한다.

(Jx에 대해서도 똑같이 생각해보자.)

즉 우리가 작성해야할 건

A번에서 선언한 start,end를 변화시킬때

B, C에 선언한 변수를 변화시키기위한 함수이다. 데이터를 추가시키고, 제외시키고..

그게 mo's 유형을 푸는 전부이다.

 

대표 문제를 통한 적용

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

13547번: 수열과 쿼리 5

이 문제를 보자.

• i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다.

만약에 범위가 늘어난다면, 서로 다른 수의 개수는 i~j에 있던 수가 아닌 수가 추가되면 서로 다른 수의 개수도 늘어날 것이고, 이미 있는 수라면 그대로일 것이다.

만약에 범위가 줄어든다면, 서로 다른 수의 개수는 i~j에 1개만 있는 수가 제외되면 서로 다른 수의 개수도 줄어들 것이고,

여러개 있는 수라면 제외시켜도 그대로일 것이다.

즉 우리가 필요한건

A.start, end

B.cnt # start,end내 서로 다른 수의 개수

C.counter # counter[num]: 범위 내 숫자 num의 개수

def add(val):
    # 숫자 val을 추가한다.
    new = cnt
    if counter[val] == 0:  # 만약 범위 내 없는 숫자였으면
        new += 1
    counter[val] += 1
    return new  # 그대로거나 하나 늘었거나


def dele(val):
    # 숫자 val을 제외한다.
    new = cnt
    counter[val] -= 1
    if counter[val] == 0:  # 만약 제외했을 때 범위에서 0개가 된다면
        new -= 1
    return new  # 그대로거나 하나 줄었거나

이렇게 함수를 만들 수 있다.

커서나 이동할 때 마다 정보를 추가/ 제외시키는 함수이다.

우선 정렬한 후 첫번째 쿼리는 직접 구해준다.

# init
cnt = 0  # 목적
start, end, idx = query[0]  # 첫번쨰 쿼리의 정보이다.
ans = [0] * M  # 정답을 담는다.
for i in range(start, end + 1):
    cnt = add(arr[i])
ans[idx] = cnt

(여기서 ans는 순서가 뒤섞인 퀴리에서 원래순서인 idx를 이용해 원래 정답을 순서대로 저장한다.)

우린 아무것도 안한 상태에서 유를 창조하고 있다. 따라서 start,end까지 add를 해준다.

for i in range(1, M):
    s, e, idx = query[i]
    while start < s:
        cnt = dele(arr[start])
        start += 1
    while start > s:
        start -= 1
        cnt = add(arr[start])
    while end < e:
        end += 1
        cnt = add(arr[end])
    while end > e:
        cnt = dele(arr[end])
        end -= 1
    ans[idx] = cnt

이제 참조할 정보가 생겼으니 두번째 쿼리부터는 순회하며 구해준다.

start,end를 현재쿼리정보인 s,e가 되게 만들어줘야한다.

start를 예를들어

start까지 추가된 상태이므로

start+1부터 추가가 안됐으므로 start+1~s까지 add해준다.

start는 이미 추가됐고 start부터 s - 1까지 dele해줘야한다.

한번 정리해보면 헷갈리지 않을것이다.

그렇게하면 ans배열이 다 채워질것이고 ans를 순차적으로 출력하면 문제를 풀 수 있다.

 

시간복잡도

데이터를 갱신할때( 우리가 상태를 갱신하기 위해 만든 함수) 시간복잡도를 F(N)이라하자.  (위 문제에선 add,dele의 시간복잡도는 O(1))이다.

start와 end를 움직이는 행위는 서로가 종속관계에 있지 않다. 따라서 따로 더해주면 된다.

end는 각 그룹내에서 빠른 순으로 정렬됐다.

따라서 각 그룹에서 end는 배열 전체를 이동할 것이다.

그룹은 sqrt(N)개 있다.

따라서 O(F(N)sqrt(N)N)

start의 경우엔

우선 같은 그룹내에서는 최대 sqrt(N)만큼 움직일 것이다.

이렇게 움직이는것의 최대 횟수는 우리가 받은 쿼리수이다.

따라서 O(F(N)sqrt(N)Q)

다른 그룹으로도 start가 이동할 수 있다.

우리는 그룹을 sqrt(N)만큼 나눴고, 다른 그룹으로 이동한다해도 최대 O(N)만큼 움직일 것이다.

따라서 O(F(N)sqrt(N)N)

따라서 복잡도는 O(F(N) * sqrt(N) * (N + Q)) 이다.

 

정리 

1. 쿼리에 원래 인덱스 정보를 포함 후 기준에 맞게 정렬한다.

2. 우리가 상태를 담기위한 배열,변수 정답을 갱신해주기위한 배열,변수를 선언해준다.

3. 두 커서를 이동시킬떄 상태를 갱신시키기위한 함수를 만들어준다.

4. 첫번쨰쿼리로 2번에서 만든 변수를 init한다.

5. 두번쨰 쿼리부터 순회한다. 

 

더 알아보기

우리가 한 그룹내에서 end를 이동할 때, 그룹내에서 마지막 쿼리는 대부분의 경우엔 배열 끝까지 갈 것이다.

또 다른 그룹이 되면 배열의 앞쪽으로 다시 이동할 것이다.

무엇인가 비효율적이다.

다시 되돌아올때 다음 그룹쿼리의 e 좌표들이 모두 포함될 것이다.

왜냐하면 현재그룹의 시작점이 i*sqrt(N) ~ (i+1)sqrt(N)이라할때 이떄 e는 i*sqrt(N)부터 N까지 이동할 것이고,

다음 그룹 시작점은 (i+1)sqrt(N)~(i+2)sqrt(N)이고 다음 그룹의 끝점은 (i+1)sqrt(N)~N에 포함될 것이기 때문이다.

따라서

(0은 짝수이다.) 짝수번째 그룹은 끝점이 증가하는 순으로, 홀수번째 그룹은 끝점이 감소하는 순으로 쿼리를 배치하면 시간을 절반으로 줄일 수 있다.

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

13553번: 수열과 쿼리 8

위 문제는 이런 테크닉이 필수이다. (python의 경우엔 갱신하는데도 최적화가 된 자료구조를 사용해야한다)

또한 일부 mo's는 세그먼트 트리로도 해결이 가능하다고 한다. 단 필자는 mo's가 구현이 더 간단해보이므로 가능하다 해도 굳이 세그트리로 풀진 않았다....