글 읽기 - 세그먼트 트리 질문있습니다!

sangjin256 9달 전 0

처음에는 계속 런타임 에러가 나서 tree의 범뮈를 최대치로 늘림으로서 런타임 에러에서는 벗어났는데

이제는 계속 틀렸다고 나옵니다. 본문에 있는 반례는 통과했는데 어디가 틀린지 모르겠습니다 ㅠㅜ

부탁드립니다!!!

import java.util.*;
public class Main{
    static long[] tree;
    static int n;
    static int arrayN;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt(), k = sc.nextInt();
        if((n&(n-1)) == 0) tree = new long[2*n];
        else tree = new long[1<<20];
        arrayN = n;
        n = tree.length/2;
        Arrays.fill(tree, 1);
        for(int i = 0; i < arrayN; i++){
            Change(i, 1, sc.nextInt(), 0, tree.length/2-1);
        }

        for(int i = 0; i < m+k; i++){
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            if(a == 1){
                if(b > 0 && b <= arrayN){
                    Change(b-1,1,c,0,tree.length/2-1);
                } 
            }
            if(a == 2){
                if(b > 0 && b <= arrayN && c > 0 && c <= arrayN && b <= c){
                    System.out.println(Multiply(b-1, c-1, 1, 0,tree.length/2-1));
                }
            }
        }
        sc.close();
    }

    public static long Change(int pos, int k, int v, int x, int y){
        if(y < pos || pos < x) return tree[k] % 1000000007;
        if(x == y) return tree[k] = v;
        int d = (x+y) / 2;
        return tree[k] = ((Change(pos,k*2,v,x,d) % 1000000007) * (Change(pos,k*2+1,v,d+1,y) % 1000000007)) % 1000000007;
    }

    public static long Multiply(int a, int b, int k, int x, int y){
        if(b < x || a > y) return 1;
        if(a <= x && y <= b) return tree[k];
        int d = (x + y) / 2;
        return ((Multiply(a, b, k*2, x, d) % 1000000007) * (Multiply(a, b, k*2+1, d+1, y) % 1000000007)) % 1000000007; 
    }
}

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

문제

문제

출처

ICPC

세그먼트 트리 질문있습니다!

sangjin256 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말