BOJ 백준 12858 Range GCD

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

 

[ 문제 요약 ]

• 배열이 주어지고 질의가 주어집니다.
• 첫 번째 숫자가 0이면 뒤에 주어지는 두수 A, B에 대해 A 번째 원소부터 B 번째 원소까지 최대공약수를 출력합니다.
• 두 번째 숫자가 0이 아니면 뒤에 주어지는 두수 A, B에 대해 A 번째 원소부터 B 번째 원소까지 첫 번째 주어지는 수를 더합니다.

 

[ 테스트 케이스 설명 ]

4// 원소 개수(1<=100,000)
6 3 38 49// 원소들 1<=1,000,000,000
5// 질의 수(1<=100,000)
0 1 3// T(0<=십억),시작위치A, 종료위치B 가주어짐
9 2 2
0 1 2// T가 0이라면, 수열의 A번째 원소부터 B번째 원소까지의 최대공약수를 출력해야 한다.
6 3 3// T가 0이 아니라면, 수열의 A번째 원소부터 B번째 원소까지에 T라는 수를 더하는 연산이다.
0 3 4
//T가 0인 연산은 하나 이상 주어진다.T가 0인 연산이 주어질 때마다 A~B원소까지 최대 공약수 출력
//이하 답
1
6
1

 

[ 알고리즘 분류 ]

• 수학
• 자료 구조
• 정수론
• 세그먼트 트리
• 느리게 갱신되는 세그먼트 트리
• 유클리드 호제법
• 차분 배열 트릭

 

[ 문제 해설 ]

이 문제를 풀기 위해서는 최대 공약수의 특징을 알아야 합니다. 먼저 gcd(a, b, c, d)는 gcd(a, b-a, c-b, d-c) 와 같이 풀어쓸 수 있습니다.

 

gcd(a, b-a, c-b, d-c) 와 같이 풀어썼을 때 특징은, 처음에 시작하는 a는 그대로 쓰고, 그 뒤부터 b-a, c-b, d-c 는 차이만 사용한다는 특징이 있습니다.

 

그러므로 구간 쿼리가 주어질 때, a는 본래 값 자체를 가져오고, 나머지는 차분 값을 가져와 연산하면 됩니다.

 

이 문제를 풀기 위해 2개의 세그먼트 트리가 사용됩니다.

 

위 gcd 식에서 a 값만을 가져올 때 사용할 일반 세그먼트 트리 하나와, 차분 값을 리프 노드로 가지며 내부 노드는 gcd를 저장할 세그먼트 트리가 필요합니다.

 

pointSeg : 세그먼트 트리 배열로, 리프 노드에 값만 저장하고 내부 노드는 아무것도 저장하지 않습니다. 구간 업데이트(lazy update)를 해야 합니다. 위에서 말한 a값만을 가져올 때 사용할 트리 입니다.

 

diffSeg : 차분을 담을 세그먼트 트리 배열로 리프 노드에는 차분 값을 저장하고, 내부 노드에는 gcd 값을 저장합니다. 차분 값을 저장할 경우, 첫 번째 값은 안 쓰는 것이 되므로 update나 query 할 때 인덱스에 대해 디테일하게 맞춰주어야 합니다.(코드 참고)

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	
	static int N, Q;
	static long arr[];
	static long lazy[];
	static long diffSeg[];// 리프노드는 배열의 차를 저장하고, 내부노드는 gcd를 저장한다.
	static long pointSeg[];// 이 세그먼트는 그냥 리프노드에 값만 저장하고 lazy 업데이트를 적용할 수 있다.
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());//원소 개수 (1 ≤ N ≤ 100,000)
		arr = new long[N + 2];
		lazy = new long[N * 4];
		diffSeg = new long[N * 4];
		pointSeg = new long[N * 4];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)// 수열의 원소 값(1<=10억)
			arr[i] = Long.parseLong(st.nextToken());
		
		init(1, 1, N);// diffSeg와 pointSeg를 업데이트한다.
		
		Q = Integer.parseInt(br.readLine());// 쿼리 수(1 ≤ Q ≤ 100,000)
		while(Q-->0)
		{
			st = new StringTokenizer(br.readLine());
			int T = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			if(T == 0)// T A B : T가 0이라면, 수열의 A번째 원소부터 B번째 원소까지의 최대공약수를 출력해야 한다.
			{
				long first = pointQuery(1, 1, N, A);
				long diff = diffQuery(1, 1, N, A, B-1);
				
				sb.append( gcd( first, Math.abs(diff)) ).append('\n');
				continue;
			}
			
			// T A B : T가 0이 아니라면, 수열의 A번째 원소부터 B번째 원소까지에 T라는 수를 더하는 연산이다.
			pointUpdate(1, 1, N, A, B, T);
			diffUpdate(1, 1, N, A - 1, T);
			diffUpdate(1, 1, N, B, -T);
		}
		System.out.print(sb);
	}
	public static void diffUpdate(int treeNode, int s, int e, int targetIdx, long value) {
		if(e < targetIdx || targetIdx < s)
			return;
		if(s == e)
		{
			diffSeg[treeNode] += value;
			return;
		}
		
		int mid = (s + e) >> 1;
		
		diffUpdate(treeNode << 1, s, mid, targetIdx, value);
		diffUpdate(treeNode << 1 | 1, mid + 1, e, targetIdx, value);
		
		diffSeg[treeNode] = gcd(diffSeg[treeNode << 1], diffSeg[treeNode << 1 | 1]);
	}
	public static long diffQuery(int treeNode, int s, int e, int left, int right) {
		if(e < left || right < s)
			return 0;
		
		if(left <= s && e <= right)
			return diffSeg[treeNode];
		
		int mid = (s + e) >> 1;
		
		long l = diffQuery(treeNode << 1, s, mid, left, right);
		long r = diffQuery(treeNode << 1 | 1, mid + 1, e, left, right);
		
		return gcd(l, r);
	}
	public static void pointUpdate(int treeNode, int s, int e, int left, int right, long value) {
		propagate(treeNode, s, e);
		
		if(e < left || right < s)
			return;
		
		if(left <= s && e <= right)
		{
			lazy[treeNode] = value;
			propagate(treeNode, s, e);
			return;
		}
		
		int mid = (s + e) >> 1;
		
		pointUpdate(treeNode << 1, s, mid, left, right, value);
		pointUpdate(treeNode << 1 | 1, mid + 1, e, left, right, value);
	}
	public static long pointQuery(int treeNode, int s, int e, int targetIdx) {
		propagate(treeNode, s, e);
		
		if(e < targetIdx || targetIdx < s)
			return 0;
		if(s == e)
			return pointSeg[treeNode];
		
		int mid = (s + e) >> 1;
		
		return targetIdx <= mid ? 
				pointQuery(treeNode << 1, s, mid, targetIdx)
				: pointQuery(treeNode << 1 | 1, mid + 1, e, targetIdx);
	}
	public static void propagate(int treeNode, int s, int e) {
		if(lazy[treeNode] == 0)
			return;
		
		if(s == e)
			pointSeg[treeNode] += lazy[treeNode];
		
		if(s != e)
		{
			lazy[treeNode << 1] += lazy[treeNode];
			lazy[treeNode << 1 | 1] += lazy[treeNode];
		}
		
		lazy[treeNode] = 0;
	}
	public static void init(int treeNode, int s, int e) {
		if(s == e)
		{
			pointSeg[treeNode] = arr[s];
			diffSeg[treeNode] = arr[s + 1] - arr[s];
			return;
		}
		
		int mid = (s + e) >> 1;
		
		init(treeNode << 1, s, mid);
		init(treeNode << 1 | 1, mid + 1, e);
		
		diffSeg[treeNode] = gcd(diffSeg[treeNode << 1], diffSeg[treeNode << 1 | 1]);
	}
	public static long gcd(long a, long b) {
		return b == 0 ? a :  gcd(b, a % b);
	}
	
}