[백준] 구간 곱 구하기

구간 곱 구하기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

30639

10766

8036

33.275%

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 48이 될 것이다.

입력

첫째 줄에 수의 개수 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로 나눈 나머지를 출력한다.

---

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<long> tree;
const int MOD = 1000000007;

// 구간 곱을 계산하는 함수 (s에서 e까지)
long GetMul(int s, int e)
{
	long partMul = 1; // 곱셈 결과를 저장할 변수

	// s와 e가 동일할 때까지 반복 (구간이 끝날 때까지)
	while (s <= e)
	{
		// s가 홀수인 경우, 왼쪽 자식 노드를 곱해주고 s를 한 칸 오른쪽으로 이동
		if (s % 2 == 1)
		{
			partMul = (partMul * tree[s]) % MOD;
			s++;
		}

		// e가 짝수인 경우, 오른쪽 자식 노드를 곱해주고 e를 한 칸 왼쪽으로 이동
		if (e % 2 == 0)
		{
			partMul = (partMul * tree[e]) % MOD;
			e--;
		}

		// s와 e를 부모 노드로 올라가면서 갱신
		s /= 2;
		e /= 2;
	}

	return partMul; // 구간 곱 반환
}

// 세그먼트 트리에서 특정 인덱스의 값을 변경하는 함수
void ChangeVal(int index, long val)
{
	// 트리에서 해당 인덱스 값을 새로 변경
	tree[index] = val;

	// 부모 노드를 갱신
	while (index > 1)
	{
		index /= 2;
		// 부모 노드는 자식 노드들의 곱으로 갱신
		tree[index] = (tree[2 * index] * tree[2 * index + 1]) % MOD;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, K;
	cin >> N >> M >> K;

	// 세그먼트 트리의 높이를 계산
	int treeHeight = 0;
	int length = N;
	while (length != 0)
	{
		length /= 2;  // 2로 계속 나누면서 트리의 높이를 구함
		treeHeight++;
	}

	// 세그먼트 트리의 크기 계산 (2^(treeHeight + 1)) 크기의 트리 배열을 만든다
	int treeSize = int(pow(2, treeHeight + 1));
	// 트리의 리프 노드 시작 인덱스를 계산
	int leftNodeStartIndex = treeSize / 2;
	// 세그먼트 트리 배열을 크기만큼 할당
	tree.resize(treeSize);

	// 트리 초기화 (세그먼트 트리의 기본값을 1로 설정)
	fill(tree.begin(), tree.end(), 1);

	// 리프 노드에 초기 값을 입력받음
	for (int i = 0; i < N; i++)
	{
		cin >> tree[leftNodeStartIndex + i];  // 리프 노드에 값을 채움
	}

	// 리프 노드를 기반으로 부모 노드들을 갱신
	for (int i = leftNodeStartIndex - 1; i >= 1; i--)
	{
		// 부모 노드는 자식들의 곱으로 갱신
		tree[i] = (tree[2 * i] * tree[2 * i + 1]) % MOD;
	}

	// 쿼리 처리
	for (int i = 0; i < M + K; i++)
	{
		long a, s, e;
		cin >> a >> s >> e;

		// 쿼리 종류가 1이면 값을 변경하는 연산
		if (a == 1)
		{
			// ChangeVal은 1-based 인덱스이므로 s-1을 더하여 0-based로 변환
			ChangeVal(leftNodeStartIndex + s - 1, e);
		}
		// 쿼리 종류가 2이면 구간 곱을 구하는 연산
		else if (a == 2)
		{
			// 구간에 대한 인덱스를 0-based로 변환하여 GetMul 함수 호출
			s += leftNodeStartIndex - 1;
			e += leftNodeStartIndex - 1;
			cout << GetMul(s, e) << "\n";
		}
	}

	return 0;
}

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