백준_11505_구간 곱 구하기(자바)

문제 링크 : https://www.acmicpc.net/problem/11505

문제

어떤 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. segment tree
   전형적인 세그먼트 트리 연습 문제이다.
   다만 update에 있어 기존의 세그먼트 트리의 경우 diff(차이값)만큼 값을 갱신해주는 방식(top-down)인데 이렇게 하면 구간 곱의 경우는 에러가 있다.
   바로 tree가 0이 되는 경우.
   요소의 값이 0이라 tree의 값도 0이 되는 순간 diff만큼 계산해주는 방식은 통하지 않는다. ( 내가 처음 그렇게 풀었다가 순간 당황했다. )
   그래서 update도 init과 비슷하게 bottom-up으로 접근했다.

2. modular
   그리고 출력은 모듈러 연산의 특징을 이용
   (a mod d) (b mod d) mod d = (a * b) mod d
   그냥 모든 구간에 1,000,000,007을 나눈 나머지 값을 더해줘도 된다. (지금 보면 tree 자료형도 굳이 long으로 안했어도 됐을 것 같다.)

코드

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

public class BOJ_11505_구간곱구하기 {
    static final int MAX_N = 1_000_000_007;
    static int N, M, K;
    static int[] arr;
    static long[] tree;
    public static void main(String[] args) throws Exception{
        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 int[N+1];
        tree = new long[N*4];

        for (int i=1;i<=N;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        init(1, 1, N);

        for (int i=0;i<M+K;i++){
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            switch (t){
                case 1: // 값 변경
                    int idx = Integer.parseInt(st.nextToken());
                    int value = Integer.parseInt(st.nextToken());

                    arr[idx] = value;
                    update(1, 1, N, idx);
                    break;

                case 2: // 구간 곱 구하기
                    int left = Integer.parseInt(st.nextToken());
                    int right = Integer.parseInt(st.nextToken());

                    long ans = multi(1, 1, N, left, right);
                    System.out.println(ans);
                    break;
            }
        }
    }

    static long init(int node, int start, int end){
        if(start == end) return tree[node] = arr[start];

        int mid = (start + end) / 2;
        long a = init(node*2, start, mid);
        long b = init(node*2+1, mid+1, end);

        return tree[node] = a*b % MAX_N;
    }

    // 바뀔 값 입력
    static long update(int node, int start, int end, int idx){
        // 범위가 벗어난 경우
        if(idx < start || idx > end) return tree[node];

        // tree[node]의 값에는 arr[idx](변경전) 값이 무조건 곱해져있으므로 딱 나누어 떨어짐

        if(start == end) return tree[node] = arr[start];
        int mid = (start + end) / 2;
        long a = update(node*2, start, mid, idx);
        long b = update(node*2+1, mid+1, end, idx);

        return tree[node] = a*b % MAX_N;
    }

    static long multi(int node, int start, int end, int left, int right){
        // 범위 밖이라면
        if(left > end || right < start) return 1;
        // 범위에 완전히 포함된 경우
        if(left <= start && right >= end) return tree[node];

        int mid = (start + end) / 2;
        long a = multi(node*2, start, mid, left, right);
        long b = multi(node*2+1, mid+1, end, left, right);

        return a*b % MAX_N;
    }
}

소감

최근 삼성dx특강 듣다가 세그먼트 트리에 자신감이 붙어 편하게 풀었던 것 같다. 중간에 삐걱거리긴 했지만...올만에 돌아온 알고리즘 타임...