[Do It! 코딩테스트 자바편(김종관)] 문제 073(백준 11505번)

느낀점

• 문제 71을 바탕으로 수정해야 하는 문제
• 곱셈의 특성상 구간의 곱을 가지고 있으면 무수히 커질 수 있기 때문에 문제에서 모듈러 연산을 요구한다(한 노드에 최대 백만이 최대, 이런 노드가 백만까지 주어질 수 있음. 그럼 최대 백만의 백만 제곱이 되는데… 롱의 최대 범위는 대략 2의 63제곱(대략 10의 18제곱)이니까 백만의 백만 제곱은 어마무시하게 큼)
• 최종 결과에만 모듈러연산을 해준다면, 중간에 노드가 가지고 있는 값이 Overflow 될 수 있으므로 노드가 가진 값을 갱신할 때도 % 연산을 해야 함

문제

구간 곱 구하기(백준: 11505번)

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int nodeCnt, changeCnt, mulCnt;
    static long[] tree;
    static final int MOD = 1000000007;
    static int powTwoK;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        nodeCnt = Integer.parseInt(st.nextToken());
        changeCnt = Integer.parseInt(st.nextToken());
        mulCnt = Integer.parseInt(st.nextToken());

        // powTwoK 구하기
        int exponext = 0;
        while (powTwoK < nodeCnt) {
            powTwoK = (int) Math.pow(2, exponext);
            exponext++;
        }
        // tree 초기화
        setTree(br);

        for (int i = 1; i <= changeCnt + mulCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (a == 1) {
                long c = Long.parseLong(st.nextToken());
                update(b, c);
            } else if (a == 2) {
                int c = Integer.parseInt(st.nextToken());
                System.out.println(getMul(b, c));
            }
        }
    }

    private static long getMul(int s, int e) {
        s = s + powTwoK - 1;
        e = e + powTwoK - 1;

        long partMul = 1;
        while (s <= e) {
            if (s % 2 == 1)
                partMul = partMul * tree[s] % MOD;
            if (e % 2 == 0)
                partMul = partMul * tree[e] % MOD;
            s = (s + 1) / 2;
            e = (e - 1) / 2;
        }

        return partMul;
    }

    private static void update(int fromIdx, long to) {
        fromIdx = fromIdx + powTwoK - 1;

        for (int i = fromIdx; i >= 1; i /= 2) {
            if (i == fromIdx) {
                tree[i] = to;
            } else {
                tree[i] = (tree[2 * i] * tree[2 * i + 1]) % MOD;
            }
        }
    }

    private static void setTree(BufferedReader br) throws IOException {
        tree = new long[powTwoK * 2];
        Arrays.fill(tree, 1);
        for (int i = powTwoK; i <= nodeCnt + powTwoK - 1; i++) {
            long tmp = Long.parseLong(br.readLine());
            tree[i] = tmp;
        }
        for (int i = powTwoK - 1; i >= 1; i--) {
            tree[i] = (tree[2 * i] * tree[2 * i + 1]) % MOD;
        }
    }

}