글 읽기 - 반례좀 찾아주세요, 아무리 머리를 굴려도 틀린 이유를 모르겠습니다.

dhtpqjagns 4년 전 0

C언어로 짠건데 C언어로 돌리면 런타임에러가 나고, C++로 돌리면 틀렸다고 나오네요.

#include <stdio.h>
    long long N[1000100];
    long long V[2000100];
    long long Segment(int index,int start, int end){//세그먼트 트리 제작
        if(start==end){
            V[index]=N[start];
            return V[index];
        }
        int mid=(start+end)/2;
        V[index]=Segment(index*2,start,mid)+Segment(index*2+1,mid+1,end);
        return V[index];
    }
    long long Change(int index,long long diff,int key,int start,int end){//업데이트
        if(key<start||key>end){
            return 0;
        }
        V[index]-=diff;
        if(start!=end){
            Change(index*2,diff,key,start,(start+end)/2);
            Change(index*2+1,diff,key,(start+end)/2+1,end);
        }
        return 0;
    }
    long long All(int start, int end, int left, int right,int index){//출력
        if(start>right||end<left){
            return 0;
        }else if(start>=left&&end<=right){
            return V[index];
        }else{
            return All(start,(start+end)/2,left,right,index*2)+All((start+end)/2+1,end,left,right,index*2+1);
        }
    }
int main(){
    int n,m,k;
    
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&N[i]);
    }
    Segment(1,1,n);
    for(int i=1;i<=m+k;i++){
        long long a,b,c;
        scanf("%lld %lld %lld",&a,&b,&c);
        if(a==1){
            Change(1,N[b]-c,b,1,n);
            N[b]=c;
            
        }else if(a==2){
            long long d=All(1,n,b,c,1);
            printf("%lld\n",d);
        }
    }
    return 0;
}

djm03178 4년 전 1

트리의 크기를 단순히 2배로 잡으면 안 됩니다. 대충 계산하려면 4배를 잡는 것이 안전하고, 정확하게 하려면 log2값을 구하고 올림한 값을 x라고 할 때 x^(x+1)만큼의 크기를 잡아줘야 합니다.

dhtpqjagns 4년 전 0

감사합니다. 그게 문제였군요. 전혀 모르고 있었네요.

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

문제

문제

출처

ICPC

반례좀 찾아주세요, 아무리 머리를 굴려도 틀린 이유를 모르겠습니다.

dhtpqjagns 4년 전 0

djm03178 4년 전 1

dhtpqjagns 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말