BOJ 12858 Range GCD

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

12858번: Range GCD

gcd(a, b, c, d, e) = gcd(a, |b - a|, |c - b|, |d- c|, |e - d|) 임을 이용해야 한다. (이 부분이 핵심이다)

어떤 구간에 속한 모든 원소에 x를 더한 더하는 경우, 그 구간 내에서 이웃한 원소들 사이의 차이는 변화가 없다. 그 구간의 경계에 인접한 원소와의 차이에만 변화가 발생한다.

GCD를 계산하기 위한 세그먼트 트리에는 인접한 원소들 사이의 차이를 저장한다.

가령, 주어진 숫자가 [6, 3, 38, 49] 라면, 세그먼트 트리에는 [6 = |0-6|, 3 = |6-3|, 35 = |3-38|, 11 = |38-49|, 49 = |49-0|]을 저장한다. 코너 케이스를 피하기 위해 첫 번째 원소를 추가한다. 구간 [1, 3]의 gcd는 gcd(6, |6 - 3|, |38-3|) =  gcd(6, gcd(|6-3|, |38-3|)) = gcd(6, gcd(3, 35)), 즉 주어진 구간의 첫 번째 숫자와 diff를 구성하는 세그먼트 트리의 gcd쿼리 결과의 gcd로 구할 수 있다.

원래 배열의 [2, 3] 구간에 9를 더하면 배열은 [6, 12, 47, 49]가 되고 세그먼트 트리는 [6, 6, 35, 2, 49]가 된다. 구간 업데이트 속에 위치한 세번째 원소가 35로 유지된다. 구간 업데이트의 경계에 해당하는 두 번째와 네 번째 원소가 각각 3->6, 11->2로 변경되었다. 

구간합의 업데이트를 위해서는 lazy segment tree를 이용할 수 있다. 구간 업데이트 단일 원소 쿼리이기 때문에, 일반 segment tree로도 가능한다.