글 읽기 - 구간곱 틀린 이유를 모르겠습니다.

convert7342 4년 전 0

세그먼트 트리 이용해 구현했습니다.

처음에는 b값으로 나누고 c를 곱하는 방식으로 했는데 질문글 찾아보니 안되는 이유가 있어서

해당 인덱스의 리프노드를 c로 바꾸고 다시 갱신해나가는 방법을 택했습니다.

MOD 연산이 잘못된건지 자꾸 틀렸다고 나오는데 도움 좀 구하고싶습니다 ㅠ

#include <bits/stdc++.h>
#define MAX 1000001
#define MOD 1000000007

using namespace std;
typedef long long lld;

vector<lld>tree;
vector<lld>arr;

int N,M,K;
lld a, b ,changer;

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

lld getMul(int node, int start, int end, int left, int right) {
	int mid = (start + end) / 2;
	if(left > end || right < start) return 1;
	if(left <= start && end <= right) return tree[node];
	
	return tree[node] = (getMul(node * 2, start, mid, left, right) % MOD) * (getMul(node * 2 + 1, mid + 1, end, left, right) % MOD) % MOD;
}

lld update(int node, int start, int end, lld idx) {
	if(!(start <= idx && idx <= end)) return tree[node] % MOD;
	if(start == end) return tree[node] = changer % MOD;
	
	int mid = (start + end) / 2;
	return tree[node] = (update(node * 2, start, mid, idx) % MOD) * (update(node * 2 + 1, mid + 1, end, idx) % MOD) % MOD;
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	tree.resize(MAX * 4);
	arr.resize(MAX);
	
	cin >> N >> M >> K;
	M += K;
	for(int i = 0 ; i < N ; i++) {
		cin >> arr[i];
	}
	
	init(0, N - 1, 1);
	
	while(M--) {
		cin >> a >> b >> changer;
		if(a == 1) {
			update(1, 0, N - 1, b - 1);
		}
		
		else if(a == 2) {
			cout << getMul(1, 0, N - 1, b - 1, changer - 1) % MOD << '\n';
		}
	}
	return 0;
}

kyo20111 4년 전 2

getMul 함수에서 tree[node]를 갱신해 주면 안됩니다.

0~3 크기의 배열에서 0~2구간의 곱을 찾는다 했을때

0~3의 곱을 저장하고 있어야할 구간에 0~2구간의 곱을 저장하게 됩니다.

kyo20111 4년 전 2

아래 출력하는 두 구간이 다른데 같은 값을 출력하게 됩니다.

intput : 
4 2 1
1
3
4
5
1 1 2
2 1 3
2 1 4

output :
24
24

ans :
24
120

convert7342 4년 전 1

감사드립니다 ㅠㅠ

아무리 읽어도 못찾겠었는데 설명까지 해주시다니..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

구간곱 틀린 이유를 모르겠습니다.

convert7342 4년 전 0

kyo20111 4년 전 2

kyo20111 4년 전 2

convert7342 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말