글 읽기 - 진짜 모르겠습니다.. 7번시도했어요

jinny 3년 전 0

5%에서 틀리길래 질문게시판 보니까 보통 범위 문제인것 같아서 long long 써야할 곳은 long long 으로 사용했는데

계속 틀립니다.. 세그먼트트리문제는 처음 풀어봐서 블로그에서 참고하며 짠건데 정말 어디가 틀렸는지 모르겠어요..

이유와 해답 알려주시면 갑사하겠습니다.

제발 도와주십쇼

/*구간 합 구하기*/
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int N, M, K;
long long arr[1000001];
vector<long long> treeV;

long long makeT(int node, int s, int e) {
	if (s == e)return treeV[node] = arr[s];

	int mid = (s + e) / 2;
	return treeV[node] = makeT(node * 2, s, mid) + makeT(node * 2 + 1, mid + 1, e);
}

void updateT(int node, int s, int e, int idx, long long diff) {
	if (idx<s || idx>e)return;
	treeV[node] += diff;

	if (s != e) {
		int mid = (s + e) / 2;
		updateT(node * 2, s, mid, idx, diff);
		updateT(node * 2 + 1, mid + 1, e, idx, diff);
	}
}

long long sumT(int node, int s, int e, int l, int r) {
	if (l > e || s > r)return 0;
	if (l <= s && r >= e)return treeV[node];

	int mid = (s + e) / 2;
	return treeV[node] = sumT(node * 2, s, mid, l, r) + sumT(node * 2 + 1, mid+1, e, l, r);
}

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

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)cin >> arr[i];
	int tree_height = (int)ceil(log2(N));
	int tree_size = (1 << (tree_height + 1));
	treeV.resize(tree_size);
	makeT(1, 0, N - 1);

	for (int i = 0; i < M + K; i++) {
		int a;
		long long b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			updateT(1, 0, N - 1, b - 1, c - arr[b - 1]);
			arr[b - 1] = c;
		}
		else cout << sumT(1, 0, N - 1, b - 1, c - 1) << "\n";
	}
}

harinboy 3년 전 1

범인은 34번째 줄입니다.

구간 합을 구하는 과정에서 세그먼트 트리가 수정되면 안 되죠.

jinny 3년 전 0

우와... 한시간동안 틀린 부분만 찾았는데 진짜 금방찾으시네요. 정말 너무너무 감사드려요!!!

rnaos1234 2년 전 0

반례찾다가 여기까지 왔는데 저랑 똑같은부분에서 틀리셨네요 덕분에 깨우치고 갑니다

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

문제

문제

출처

ICPC

진짜 모르겠습니다.. 7번시도했어요

jinny 3년 전 0

harinboy 3년 전 1

jinny 3년 전 0

rnaos1234 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말