[ BOJ ][JAVA][11505] 구간 곱 구하기

https://www.acmicpc.net/problem/11505

11505번: 구간 곱 구하기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	9466	3309	2348	33.080%

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 48이 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1 번째 줄까지 세 개의 정수 a,b,c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b부터 c까지의 곱을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 0보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 곱을 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 5 2
2 3 5

예제 출력 1

240
48

예제 입력 2

5 2 2
1
2
3
4
5
1 3 0
2 2 5
1 3 6
2 2 5

예제 출력 2

0
240

코드

/*
    구간 곱 구하기
    세그먼트 트리
*/
import java.io.*;
import java.util.*;
public class p11505 {
    static class SegmentTree {
        long[] tree;
        int s;
        public SegmentTree(int size) {
            int h = (int) Math.ceil(Math.log(size) / Math.log(2));
            this.s = (int) Math.pow(2, h + 1);
            // tree의 사이즈는 s로 잡아도 되지만 넉넉하게 곱하기 4로 잡는것도 좋다.
            tree = new long[n * 4];
        }

        static long init(long[] tree, int node, int start, int end) {
            if (start == end) return tree[node] = arr[start];
            int mid = (start + end) / 2;
            return tree[node] = init(tree, node * 2, start, mid) * init(tree, node * 2 + 1, mid + 1, end) % MOD;
        }

        static long update(long[] tree, int node, int start, int end, int idx, long val) {
            // idx의 범위가 tree의 범위에 벗어나면 종료조건
            if (start > idx || idx > end) return tree[node];
            //tree[node] = val;
            if(start == end) {
                return tree[node] = val;
            }
            int mid = (start + end) / 2;
            return tree[node] = update(tree, node * 2, start, mid, idx, val) * update(tree, node * 2 + 1, mid + 1, end, idx, val) % MOD;
        }

        // [start, end] : SegmentTree의 처음과 끝 인덱스 (재귀를 할 때마다 start, end가 변경)
        // [left, right] : 연산을 수행할 인덱스의 범위 (b, c는 그대로 동일)
        static long multi(long[] tree, int node, int start, int end, int left, int right) {
            // start, end가 범위(left, right)에 벗어나면 종료
            if (left > end || right < start) return 1;
            if (left <= start && end <= right) {
                return tree[node];
            }
            int mid = (start + end) / 2;
            return (multi(tree, node * 2, start, mid, left, right)) 
                * (multi(tree, node * 2 + 1, mid + 1, end, left, right)) % MOD;
        }
    }
    static final int MOD = 1000000007;
    static int n, m, k;
    static long[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        arr = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        SegmentTree sgTree = new SegmentTree(n);
        sgTree.init(sgTree.tree, 1, 1, n);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m + k; i++) {
            st = new StringTokenizer(br.readLine());
            int command = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            switch(command) {
            case 1:
                // b번째 수를 c로 바꾼다.
                arr[b] = c;
                sgTree.update(sgTree.tree, 1, 1, n, b, c);
                break;
            case 2:
                // b번째 수부터 c번째 수 까지 곱을 구하여 출력한다.
                long ret = sgTree.multi(sgTree.tree, 1, 1, n, b, c);
                sb.append(ret % MOD).append("\n");
                break;
            }
        }
        System.out.println(sb.toString());
    }
}