글 읽기 - 2042번 구간합 구하기 5%에서 계속 틀립니다 ㅠㅠ

gkfkagkfka12 6년 전 0

주석 적은 건 신경안쓰셔도 되고 어느 부분이 틀린지 반례좀 들어주시면 감사하겠습니다.

주석처럼 다 출력해서 과정 살펴봤는데도 어디가 문제인지를 모르겠습니다...ㅠ

a,b,c 모두 100만 이하니까 int로 커버되고 나머지는 long long 범위 넘지 않는다고 했으니까 다 long long으로 해줬는데 뭐가 문제일까요?

#include <iostream>
#include <cmath>
#include <cstdio>

typedef long long ll;

ll sum(ll tree[], int node, int start, int end, int left, int right)
{
	if (left > end || right < start) return 0;
	if (left <= start && right >= end) {
		std::cout << start << " 부터 " << end << " 까지의 합\n";
		return tree[node];
	}
	
	int mid = (start + end) / 2;
	return sum(tree, node * 2, start, mid, left, right) + sum(tree, node * 2 + 1, mid + 1, end, left, right);
}


// 세그먼트 트리의 어떤 노드 값을 변경했을 때 그에 관련된 모든 노드의 값을 갱신하는 함수
void update(ll tree[], int node, int start, int end, int index, ll diff)
{
	std::cout << start << " 부터 " << end << " 까지 ";
	// 부분합 범위에 index가 포함되지 않을 경우 함수를 종료한다.
	if (start > index || end < index) {
		std::cout << "인덱스 범위 벗어남\n";
		return;
	}

	// 포함될 경우 diff(바꾼 숫자와 기존 숫자의 차이)를 더해주어 갱신한다.
	std::cout << tree[node] << "에 " << diff << "만큼 더해져서 ";
	tree[node] += diff;
	std::cout << tree[node] << "가 됨\n";

	// 숫자를 변경한 노드를 만날때까지 지속한다.
	if (start != end) {
		// 이것도 init함수의 원리와 동일하게 자식노드들로 index 범위에 포함되면 갱신하는 형태
		int mid = (start + end) / 2;
		update(tree, node * 2, start, mid, index, diff);
		update(tree, node * 2 + 1, mid + 1, end, index, diff);
	}
}

// 부분합 노드로 세그먼트 트리를 초기화하는 함수
ll init(ll tree[], ll arr[], int node, int start, int end)
{
	// 리프노드일 경우 배열 값이므로 그대로 초기화
	if (start == end) return tree[node] = arr[start];

	// 구간을 나눠야 하는데 그 기준을 mid로 잡는다.
	int mid = (start + end) / 2;

	// 다시 init함수를 호출하여 현재 노드의 자식노드들 즉 node*2와 node*2+1로 부분합을 구하게 한다.
	// 이 호출로 인해 결국 리프노드까지 도달하게 되며 호출이 종료되고 루트노드까지 올라오는 방식이다.
	return tree[node] = init(tree, arr, node * 2, start, mid) + init(tree, arr, node * 2 + 1, mid + 1, end);
}

int main(void)
{
	int n, m, k; std::cin >> n >> m >> k;

	// arr의 인덱스는 0부터 시작
	ll *arr = new ll[n];
	for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);

	// 세그먼트 트리 높이와 할당할 배열의 크기 구하기
	int h = static_cast<int>(std::ceil(std::log2(n))) + 1;
	int tree_size = static_cast<int>(std::pow(2.0, h));

	// tree의 인덱스는 1부터 시작 (노드 1번)
	ll *tree = new ll[tree_size];

	// 세그먼트 트리 초기화
	init(tree, arr, 1, 0, n - 1);

	int a, b, c;
	for (int i = 0; i < m + k; i++) {
		scanf("%d %d %d", &a, &b, &c);
		b--;
		if (a == 1){
			ll diff = (arr[b] - c) * -1; arr[b] = c;
			update(tree, 1, 0, n - 1, b, diff);
		}
		else if (a == 2) printf("%lld\n", sum(tree, 1, 0, n - 1, b, c - 1));
	}


	delete[] arr, tree;

	return 0;
}

juhongkim2 6년 전 2

80번째 줄에서

arr[b]=c 이거 update해주는 부분이죠?

업데이트는 a==1일때만 실행되어야 하는데 80번째줄 처럼 하면 arr[b]값이 a==2일때도 바뀌어버립니다

gkfkagkfka12 6년 전 0

소스를 그렇게 수정했는데도 틀리네요...ㅠ

gkfkagkfka12 6년 전 0

죄송합니다....주석을 제거안했었네요 ㅠㅠ 감사합니다!!!!

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

문제

문제

출처

ICPC

2042번 구간합 구하기 5%에서 계속 틀립니다 ㅠㅠ

gkfkagkfka12 6년 전 0

juhongkim2 6년 전 2

gkfkagkfka12 6년 전 0

gkfkagkfka12 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말