개요

백준 11505: 구간 곱 구하기

• 입력
  첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1 번째 줄까지 세 개의 정수 a,b,c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b부터 c까지의 곱을 구하여 출력하면 된다.

  입력으로 주어지는 모든 수는 0보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.

• 출력
  첫째 줄부터 K줄에 걸쳐 구한 구간의 곱을 1,000,000,007로 나눈 나머지를 출력한다.

접근 방식

1. 접근방식은 백준 2042(구간 곱 구하기) 문제와 유사하다.
   세그먼트 트리를 사용해 각 노드에 해당 노드가 관리하는 구간의 총 곱을 저장하는 방식이다.

2. 유의할 점은 부모노드가 자식노드들의 곱을 저장해야 하므로
   전체 트리를 1로 초기화를 해줬다.
   리프노드를 연산할 차례일때 초기화를 1로 안 한 상태라면 sibling리프노드 값이 0이나 쓰레기값이 들어있으므로
   부모노드 값이 0이나 쓰레기값이 저장되므로 조심해야한다.

3. 백준 2042(구간 곱 구하기) 문제와 차이점은
   곱연산이므로 트리노드를 순회하며 구간곱을 구할때
   탐색하려는 구간이 목표구간을 벗어났을 때
   백준 2042번 문제는 합이므로 0을 return하지만
   이 문제에선 곱이므로 1을 return해야한다.

4. 10억짜리 나머지 값 연산을 빼먹지말고 해야한다.

전체 코드

#include<iostream>

using namespace std;

//사이즈 2^21 의 트리
long long Arr[2097152];
//나머지
const int Modular = 1'000'000'007;
//수의 갯수, 변경 횟수, 구간의 곱 구하는 횟수 , 첫번째 리프노드의 인덱스
int N,M,K,FirstLeafNodeIndex=1;

//목표구간 [targetL,targetR] 현재 탐색구간 [curL, curR] 현재 보고있는 노드 nodeNum
long long Mul(int targetL, int targetR, int nodeNum, int curL, int curR) {
	if (targetL > curR || targetR < curL) return 1;
	else if (targetL <= curL && targetR >= curR) return Arr[nodeNum]%Modular;

	int mid = (curL + curR) / 2;
	return Mul(targetL, targetR, nodeNum * 2, curL, mid) * Mul(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR) % Modular;

}

//변화량으로 double change =(double) c / Arr[idx];을 사용하면 안되는게 arr[idx]값이 0이나오면 division by 0되버림
void ChangeAndAdjustTree(int a, int b, int c) {
	if (a == 1) {
		int idx = b + FirstLeafNodeIndex;
		Arr[idx] = c;
		//부모 노드값 다시 세팅
		for (int i = idx / 2; i > 0; i /= 2) {
			Arr[i] = Arr[i * 2] * Arr[i * 2 + 1] % Modular;
		}

	}
	else {
		cout << Mul(b, c-1, 1, 0, FirstLeafNodeIndex - 1)<<'\n';

	}
}

void Input() {
	int a=0, b=0, c = 0;
	cin >> N >> M >> K;
	//곱이므로 1로 초기화해줌
	fill(Arr, Arr + 2097152, 1);
	//2를 계속 곱해주며 첫번째 리프노드 위치를 정함.
	while (FirstLeafNodeIndex < N) {
		FirstLeafNodeIndex *= 2;
	}
	//리프노드들 입력받음
	for (int i = 0; i < N; i++) {
		cin >> Arr[FirstLeafNodeIndex + i];
	}
	//세그먼트 트리 전체 노드 갱신해줌
	for (int i = FirstLeafNodeIndex - 1; i > 0; i--) {
		Arr[i] = Arr[i * 2]  * Arr[i * 2 + 1] % Modular;
	}
	for (int i = 0; i < M + K; i++) {
		cin >> a >> b >> c;
		ChangeAndAdjustTree(a, b-1, c);
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

ChangeAndReadjustTree 함수를 이전 문제인 백준 2042(구간 곱 구하기) 문제와 동일하게
변화량만 체크하고 부모 노드에 전부 해당 변화량만 계산해주려고

double change = (double)c / Arr[idx];
while (idx > 0) {
	Arr[idx] *= change;
	Arr[idx] %= Modular;
	idx /= 2;
}

이런식으로 구현했더니 Arr[idx]값이 0으로 바뀌었을 때 divisionByZero 오류가 나서 쓰레기값을 뱉는다.

그 후 Arr[idx]값이 0이 아닐 때와 0일때로 처리하고 0이 아닐때 저 코드를 그대로 썼으나
틀렸습니다가 떠서 이유를 곰곰이 생각해봤다.
확실친 않지만 double이 가진 오차때문이라고 생각한다.