[ 백준 11505 ] 구간 곱 구하기 : C++ 풀이

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

11505번: 구간 곱 구하기

해설

단순 세그먼트 트리의 구현 문제입니다.

 

다만 좀 주의할 점 몇가지가 있다면, 저같은 경우 query에서 범위를 벗어난 경우 -1을 반환하게 하고 아예 배제를 했는데, query 시 범위를 벗어날 경우 문제에서 요구하는 것이 구간의 곱이기 때문에 반환 값을 1로 설정해주시면 됩니다.

 

나머지 부분은 제 코드를 참고하시면 될 것 같습니다.

소스코드

#include<iostream>
using namespace std;

int seg[4000000];
int arr[1000000];
const int MOD = 1000000007;
int N, M, K;

int init(int start, int end, int node) {
	if (start == end) return seg[node] = arr[start];
	int mid = (start + end) / 2;
	return seg[node] = ((long long)init(start, mid, node * 2) * init(mid + 1, end, node * 2 + 1)) % MOD;
}

int update(int nodeLeft, int nodeRight, int idx, int val, int node) {
	if (nodeLeft > idx || nodeRight < idx) return seg[node];

	if (nodeLeft == nodeRight) return seg[node] = val;

	int mid = (nodeLeft + nodeRight) / 2;

	int leftVal = update(nodeLeft, mid, idx, val, node * 2);
	int rightVal = update(mid + 1, nodeRight, idx, val, node * 2 + 1);

	return seg[node] = (long long)leftVal * rightVal % MOD;
}

int query(int left, int right, int nodeLeft, int nodeRight, int node) {
	if (nodeLeft > right || nodeRight < left) return -1;
	if (left <= nodeLeft && nodeRight <= right) return seg[node];
	long long rtn = 0;
	int mid = (nodeLeft + nodeRight) / 2;

	int rightVal = query(left, right, nodeLeft, mid, node * 2);
	int leftVal = query(left, right, mid + 1, nodeRight, node * 2 + 1);

	if (rightVal == -1) return leftVal;
	if (leftVal == -1) return rightVal;

	return (long long)rightVal * leftVal % MOD;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < N; ++i) cin >> arr[i];
	int a, b, c;
	init(0, N - 1, 1);
	for (int i = 0; i < M + K; ++i) {
		cin >> a >> b >> c;
		if (a == 1) {
			b--;
			update(0, N - 1, b, c, 1);
		}
		else {
			b--; c--;
			cout << query(b, c, 0, N - 1, 1) << '\n';
		}
	}
}