글 읽기 - 반례가 궁금합니다.. 세그 트리입니다

kkw564 6년 전 1

init생성없이 update와 query로 세그 트리를 생성하는데

예제 문제의 세그트리 부분 쿼리에 대해서는 모든 답이 다 나오는데 다른 반례가 궁금하네요

혹시나해서 자료형문제인가싶어 모두다 ll로 바꾸어 돌려봐도 틀렸다네요 ㅠ

#include <iostream>
#include <cstdio>
#include <math.h>
#include <vector>

using namespace std;

typedef long long ll;

void update(vector<int> &arr, vector<ll> &tree, int node, int start, int end, int index, ll diff)
{
	//cout << "start :: " << start << " end :: " << end << " left :: " << left << " right :: " << right << " node :: " << node << " tree[node] :: " << tree[node] << endl;
	if (!(start <= index && index <= end))
		return;

	tree[node] += diff;
	

	if(start != end)
	{
		int mid = (start + end) / 2;

		update(arr, tree, node * 2, start, mid, index, diff);
		update(arr, tree, node * 2 + 1, mid + 1, end, index, diff);
	}
}

ll query(vector<ll> &tree, int node, int start, int end, int left, int right)
{
	if (left > end || right < start)
		return 0;

	if (left <= start && end <= right)
	{
		//cout << "start :: " << start << " end :: " << end << " left :: " << left << " right :: " << right << " node :: " << node << " tree[node] :: " << tree[node] << endl;
		return tree[node];
	}
	int mid = (start + end) / 2;

	return query(tree, node * 2, start, mid, left, right) + query(tree, node * 2 + 1, mid + 1, end, left, right);
}

int main()
{
	int n, q;

	scanf("%d %d", &n, &q);

	int h = (int)ceil(log2(n));
	int tree_size = (1 << (1 + h));

	vector<int> arr(n);
	arr.assign(n, 0);
	vector<ll> tree(tree_size);
	tree.assign(tree_size, 0);

	while (q--)
	{
		int num;

		scanf("%d", &num);

		if (num == 1)
		{
			int pos, val;
			scanf("%d %d", &pos, &val);
			ll diff = val - arr[pos - 1];
			//cout << diff << " << " << endl;
			arr[pos-1] = val;
			update(arr, tree, 1, 0, n - 1, pos-1, diff);
		}
		else if (num == 2)
		{
			int left, right;
			scanf("%d %d", &left, &right);
			printf("%lld\n",query(tree, 1, 0, n - 1, left-1, right-1));
		}


	}


	return 0;
}

pichulia 6년 전 10

문제를 잘못 이해하신거 같네요... 가계부 내용에 "추가"만 하지, "변경"하는건 없습니다.

99 3

1 1 1

2 1 1

2가 출력되어야 합니다.

kkw564 6년 전 1

감사합니다!~ 문제 이해가 어렵네요 ㅠㅠ

rootsquare 3년 전 1

쿼리 1은

해당 날짜의 값을 바꾸는 것이 아닌 변화량을 의미하는 것 같습니다.

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

문제

문제

출처

ICPC

반례가 궁금합니다.. 세그 트리입니다

kkw564 6년 전 1

pichulia 6년 전 10

kkw564 6년 전 1

rootsquare 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말