글 읽기 - 어느 부분이 문제인지 모르겠습니다...

semtax 7년 전 0

세그먼트 트리를 짜서 했는데 안되네요...

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int N,M,K;

struct RQ
{
	int N;
	vector<long long int> range;
	
	RQ() { }
	RQ(vector<long long int> &array)
	{
		N = array.size();
		range.resize(N*4);
		init(array,1,0,N-1);
	}
	
	long long int init(vector<long long int> &array,int node,int left,int right)
	{
		if(left==right)
			return range[node] = array[left];
			
		int mid = (left+right)/2;
		return range[node] = init(array,node*2,left,mid) + init(array,node*2 + 1,mid+1,right);
	}
	
	long long int query(int left,int right,int node,int nodeLeft,int nodeRight)
	{
		if(left > nodeRight || right < nodeLeft)
			return 0;
		
		if(nodeLeft >= left && nodeRight <= right)
		{
			return range[node];
		}
		
		int mid = (nodeLeft + nodeRight)/2;
		return query(left,right,node*2,nodeLeft,mid) + query(left,right,node*2 + 1,mid+1,nodeRight);
	}
	
	long long int query(int left,int right)
	{
		return query(left-1,right,1,0,N-1);
	}
	
	long long int update(int index,int value,int node,int nodeLeft,int nodeRight)
	{
		if(index > nodeRight || index < nodeLeft)
			return range[node];
		
		if(nodeLeft==nodeRight)
			return range[node] = value;
			
		int mid = (nodeLeft + nodeRight)/2;
		return range[node] = update(index,value,node*2,nodeLeft,mid) + update(index,value,node*2 + 1,mid+1,nodeRight);
	}
	
	long long int update(int index,int value)
	{
		return update(index-1,value,1,0,N-1);
	}
};

int main() {
	
	RQ rq;
	vector<long long int> array;
	long long int t,value;
	int cmd,n,a,b;
	scanf("%d %d %d",&N,&M,&K);
	
	for(int i=0;i<N;i++)
	{
		scanf("%lld",&t);
		array.push_back(t);
	}
	
	rq = RQ(array);
	
	for(int i=0;i<M+K;i++)
	{
		scanf("%d",&cmd);
		if(cmd==1)
		{
			scanf("%d %lld",&n,&value);
			rq.update(n,value);
		}
		else
		{
			scanf("%d %d",&a,&b);
			printf("%lld\n",rq.query(a,b));
		}
	}
	
	return 0;
}

yukariko 7년 전 0

세그먼트 트리에는 0번부터 N-1인데

a, b 쿼리는 1부터 N으로 가정하고 있어서 그렇습니다.

semtax 7년 전 0

감사합니다. 해결되었습니다.

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

문제

문제

출처

ICPC

어느 부분이 문제인지 모르겠습니다...

semtax 7년 전 0

yukariko 7년 전 0

semtax 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말