[Python] 백준 12858 - Range GCD

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

 

풀이

분명 느갱세의 응용 문제라고 들었는데, 느갱세 풀이는 어떻게 하는건지 생각하지도 못하고 오히려 느갱세를 안쓰는 풀이만 생각해버렸다.

 

먼저 차분 배열 트릭을 이용하면 Range Update를 딱 두 개의 노드에 대해서만 해주어도 된다는 점에서 시작하자.

그런데, 잘 생각해보면 어떤 수 a, b, c, d, e의 gcd는 유클리드 호제법에 따라 다음과 같이 구해질 수도 있다.

 

gcd(a, b, c, d, e) = gcd(a, |b-a|, |c-b|, |d-c|, |e-d|)

 

두 수의 차이는 차분 배열에서 이미 저장하고 있기 때문에, 차분 배열을 그냥 바로 세그트리화 시켜버려서 구간별 gcd를 구할 수 있을 것이다!

 

그런데 여기서 하나 고려해주어야 할 점은, 위의 식에서도 알 수 있듯이 구간의 맨 처음에는 "원본 수"가 하나 있긴 있어야 한다. 안그러면 다음 게시판과 같은 반례가 생긴다.

 

https://www.acmicpc.net/board/view/61003

 

그래서 구하고자 하는 범위의 가장 왼쪽과 오른쪽 수를 구해주고 시작할건데, 이는 차분 배열을 기반으로 합을 연산하는 세그트리를 하나 더 만들면 해결된다. l번째 원소는 search(1, l)이니까.

 

바텀업 트리로 구현할 건데,

gcd 세그트리로 돌아와서 생각해보면 맨 아래 리프노드들에는 차분 배열이 저장되어있고 그 윗 단계부터 gcd들이 저장된다. 그래서 search 함수를 적용할 때, 리프노드 단계에서는 차분배열의 수를 그냥 써주는 것이 아니라 아까 만든 또 하나의 다른 세그트리를 이용해서 원본수를 찾고, 한 층씩 올라가도록 한다(말이 잘 이해가 안되는 것 같지만 코드를 보면 알 수 있다).

 

그러니까 차분 배열 트릭과 세그트리 2개를 이용하면 느갱세 없이도 풀 수 있다. 솔직히 느갱세를 어떻게 쓴다는 것인지 아직도 모르겠다.

 

import sys
input = sys.stdin.readline
from math import gcd

N = int(input())
tmp = list(map(int, input().split()))
arr = [tmp[0]]
for i in range(1, N):
    arr.append(tmp[i] - tmp[i-1])
arr.append(0)

N += 1
size = 1
while size < N:
    size <<= 1
tree = [0]*(2*size)
tree1 = [0]*(2*size)
size -= 1

def update(idx, diff):
    idx += size
    tree[idx] += diff
    idx //= 2
    while idx:
        tree[idx] = gcd(tree[idx*2], tree[idx*2+1])
        idx //= 2

for i in range(1, N+1):
    update(i, arr[i-1])

def update1(idx, diff):
    idx += size
    while idx:
        tree1[idx] += diff
        idx //= 2

for i in range(1, N+1):
    update1(i, arr[i-1])

def search(l, r):
    ans = gcd(search1(1, l), search1(1, r))
    l += size
    r += size
    if l % 2 == 1:
        l += 1
    l //= 2
    if r % 2 == 0:
        r -= 1
    r //= 2
    while l <= r:
        if l % 2 == 1:
            ans = gcd(ans, tree[l])
            l += 1
        l //= 2
        if r % 2 == 0:
            ans = gcd(ans, tree[r])
            r -= 1
        r //= 2
    return ans

def search1(l, r):
    l += size
    r += size
    ans = 0
    while l <= r:
        if l % 2 == 1:
            ans += tree1[l]
            l += 1
        l //= 2
        if r % 2 == 0:
            ans += tree1[r]
            r -= 1
        r //= 2
    return ans

Q = int(input())
for q in range(Q):
    T, A, B = map(int, input().split())
    if T == 0:
        print(search(A, B))
    else:
        update(A, T)
        update(B+1, -T)
        update1(A, T)
        update1(B + 1, -T)