백준 11505 ( 구간 곱 구하기 )

문제

---

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

 

 

풀이

---

구간합 세그먼트 트리를 구간 곱으로 바꿔주는 것으로 풀었다.

 

1,000,000,007 로 나눈 나머지를 구하는 것이 문제기 때문에 구간 곱을 구할때 미리 modular 연산을 통해서 값을 구해 놓는다.

 

값을 update 할 때에도 같은 방식으로 modular 연산을 통해 미리 값을 1,000,000,007로 나눈 나머지로 만들어 놓는다.

 

 

<전체코드>

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;

import javax.management.Query;

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {

	static StringBuilder sb = new StringBuilder();
	static long[] tree;
	static int[] list;
	
	
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        
        tree = new long[4 * (n + 1)];
        
        list = new int[n + 1];
                
        for(int i = 1 ; i <= n ; i++) {
        	list[i] = Integer.parseInt(bufferedReader.readLine());
        }
        
        init(1, n, 1);
        
        for(int i = 0 ; i < m + k ; i++) {
        	st = new StringTokenizer(bufferedReader.readLine());
        	
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	int c = Integer.parseInt(st.nextToken());
        	
        	if( a == 1) {
        		update(1, n, 1, b, c);
        	}
        	else {
        		sb.append(query(1, n, 1, b, c) + "\n");
        	}
        	
        }
               
        
        System.out.println(sb);
    }
    
    public static long init(int start, int end, int node) {
    	
    	if(start == end) {
    		return tree[node] = list[start];
    	}
    	
    	int mid = (start + end) / 2;
    	
    	return tree[node] = (init(start, mid, 2 * node) * init(mid + 1, end, 2 * node + 1))% 1000000007;
    	
    }
    
    public static long query(int start, int end, int node, int first, int last) {
    	
    	if(start > last || end < first)
    		return 1;
    	
    	else if(first <= start && end <= last) {
    		return tree[node];
    	}
    	
    	else {
    		int mid = (start + end) / 2;
    		
    		return (query(start, mid, 2 * node, first, last) * query(mid + 1, end, 2 * node + 1 , first, last)) % 1000000007;
    	}
    }
    
    public static long update(int start, int end, int node, int idx, int val) {
    	
    	if(start == end) {
    		return tree[node] = val;
    	}
    	
    	int mid = (start + end) / 2 ;
    	
    	if(mid >= idx) {
    		return tree[node] = (tree[2 * node + 1] * update(start, mid, 2 * node, idx, val)) % 1000000007; 
    	}
    	else {
    		return tree[node] = (tree[ 2 * node] * update(mid + 1, end, 2 * node + 1, idx, val)) % 1000000007; 
    	}
    }
    
}