글 읽기 - 틀린 이유좀 찾아주실분 구합니다..

sanha93 3년 전 0

getFruit -> 구간 곱 구하는 함수

changeTree -> 값 변경하는 함수

makeTree -> 세그먼트 트리만드는 함수

입니다. changeTree는 리프부터 출발해서 올라가도록 만들었습니다.

0 이곳저곳에 넣어보기도 하고

changeTree 가 잘 작동하는지도 여러번 확인했고

트리에 1개, 2개 들어갈때도 확인을 해봤는데 못찾겠어요 ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#define DEVIDE %1000000007
using namespace std;


vector<int> tree;

queue<int> q;
vector<int> save;
int global = 1;
int lEnd, rEnd;

int getFruit(int l, int r, int fruit) {
	int mid = (l + r) / 2;
	long long  tl, tr;
	long long t;
	if (r < lEnd || l > rEnd)
		return 1;
	if (l >= lEnd && r <= rEnd) {
		return tree[fruit];
	}
	else {
		tl = getFruit(l, mid, fruit * 2);
		tr = getFruit(mid + 1, r, fruit * 2 + 1);
		t = (tl*tr)DEVIDE;
		return  t;
	}
}

void changeTree(int p, int toc) {
	// 왼쪽 노드인지, 오른쪽노드인지 판단 후, 계싼해서 위에 노드로 올림 
	int next = p / 2;
	int fr;
	long long temp;
	tree[p] = toc;
	if (p % 2 == 0) {
		fr = p + 1;
	}
	else {
		fr = p - 1;
	}
	temp = (tree[p] * tree[fr])DEVIDE;
	if(p!=1)
		changeTree(next, temp);
	
}

int makeTree(int l , int r, int fruit) {
	int mid = (l + r) / 2;
	long long  tl, tr;
	long long t;
	if (l == r) {
		tree[fruit] = q.front();
		q.pop();
		save[global] = fruit;
		global++;
		return tree[fruit];
	}
	else {
		tl = makeTree(l, mid, fruit * 2);
		tr = makeTree(mid + 1, r, fruit * 2 + 1);
		t = (tl * tr)DEVIDE;
		tree[fruit] = t;
		return  t;
	}
}

int main() {
	int n, m, k;
	int temp;
	int from, to;
	cin >> n >> m >> k;

	save.assign(n+1, 0);
	temp = 1;
	while (pow(2,temp)< n) {
		temp++;
	}
	tree.assign(pow(2, temp+1) , 0);
	for (int i = 0; i < n; i++) {
		scanf("%d", &temp);
		q.push(temp);
	}
	makeTree(0, n-1, 1);
	for (int i = 0; i < m+k; i++) {
		scanf("%d %d %d", &temp, &from, &to);
		if (temp == 2) {
			lEnd = from-1;
			rEnd = to-1;
			printf("%d\n", getFruit(0, n - 1, 1)); 
		}
		else {
			changeTree(save[from], to);
		}
	}
	return 0;
}



/*
5 200 2
1000000
900000
800000
700000
600000




*/

convert7342 3년 전 1

tree 와 q와 save의 자료형 문제로 보입니다.

구간곱을 저장하다보면 int 자료형의 범위를 넘어갈 것으로 보이네요

sanha93 3년 전 0

1000000007 로 나눈 나머지면 무조건 100000007 보다 작지 않을까요? long long 으로 계산한 후에 모드 계산으로 int 커버 할 만큼 줄인 다음에 int로 넘기는 식이라.. 이렇게하면 문제가 발생할까요?

convert7342 3년 전 1

tree의 자료형만 문제가있네요.

temp = (tree[p] * tree[fr])DEVIDE;

이런부분들을 보면 tree[p]와 tree[fr] 같은 것들은 100000007로 나눈 나머지가 저장되니 100000006이 저장되어 있다고 칩시다.

그러면 tree[p] * tree[fr]이 연산되는 과정에서 int범위를 초과하기 때문에 오버플로우가 발생합니다.

이미 연산되는과정에서 오버플로우가 발생했기때문에 연산 후에 DEVIDE를 해주더라도 오답이 발생하구요

sanha93 3년 전 0

아... 나중에 트리 바꿔줄때 그부분에서 실수한거였군요 ㅠㅠ 감사합니다..

changeTree의

temp = (tree[p] * tree[fr])DEVIDE;

해당 부분만

temp = ((long long)tree[p] * (long long)tree[fr])DEVIDE;

이렇게 바꿔주니 통과가 나오네요. 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

틀린 이유좀 찾아주실분 구합니다..

sanha93 3년 전 0

convert7342 3년 전 1

sanha93 3년 전 0

convert7342 3년 전 1

sanha93 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말