글 읽기 - 왜 틀린지 모르겠습니다..

cksdnwh 6년 전 1

세그먼트 트리를 배운지 얼마 안돼서 미숙합니다.

왜 틀렸는지 혹은 반례를 찾아주시면 감사하겠습니다.(_ _)

import java.util.Scanner;

class Main{
    static int Q = 1000000007;
    public static void main(String[] args){
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int m = scn.nextInt();
        int k = scn.nextInt();
        int h = (int)Math.ceil(Math.log(n)/Math.log(2));
        int countM=0, countK=0;
        h=1<<(1+h);
        int[] tree = new int[h+1];
        int[] arr = new int[n];
        int[] ans = new int[n];
        for(int i=0; i<n; i++)
            arr[i]=scn.nextInt();
        segment(tree,arr,1,0,n-1);
        int a, b, c;
        while(!(countM==m&&countK==k)){
            a = scn.nextInt();
            b=scn.nextInt();
            c=scn.nextInt();
            if(a==1){
                countM++;
                arr[b-1]=c;
                update(tree,1,0,n-1,b-1,c);
            } else {
                ans[countK++]=mul(tree,1,0,n-1,b-1,c-1);
            }
        }
        for(int i=0; i<k; i++)
            System.out.println(ans[i]);
    }
    public static int segment(int[] tree, int[] arr, int node, int start, int end){
        if(start==end){
            return tree[node]=arr[start]%Q;
        } else {
            int mid = (start+end)/2;
            int a = segment(tree,arr,node*2,start,mid)%Q;
            int b = segment(tree,arr,node*2+1,mid+1,end)%Q;
            return tree[node]=a*b%Q;
        }
    }
    public static int update(int[] tree, int node, int start, int end, int index, int diff){
        if(start>index||index>end)return tree[node];

        if(start==end)return tree[node]=diff;

        int mid = (start+end)/2;
        return tree[node]=update(tree, node*2, start, mid, index, diff)*update(tree,node*2+1,mid+1,end,index,diff)%Q;

    }
    public static int mul(int[] tree, int node, int start, int end, int left, int right){
        if(right<start||end<left)return 1;
        if(left<=start&&end<=right) return tree[node];
        int mid =(start+end)/2;
        return mul(tree,2*node,start,mid,left,right)*mul(tree,2*node+1,mid+1,end,left,right)%Q;
    }
}

jh05013 6년 전 1

오버플로우가 납니다.

cksdnwh 6년 전 0

한번 고쳐 보도록 하겠습니다

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

문제

문제

출처

ICPC

왜 틀린지 모르겠습니다..

cksdnwh 6년 전 1

jh05013 6년 전 1

cksdnwh 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말