[백준] 구간 곱 구하기

[hye-on]

🔗 구간 곱 구하기

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

#include<iostream>
#include<vector>

using namespace std;



int N, M, K;
typedef long long ll;

//세그먼트 트리 - 구현 기억 안남
vector<ll>v;
vector<ll>tree;
int MOD = 1000000007;


ll init(int start, int end, int node) { //v의 시작 ~끝, node: tree의 노드를 가르킴
	if (start == end)
		return tree[node] = v[start];
	int mid = (start + end) / 2;
	//재귀적으로 두 구간으로 나누고 그 곱을 나로  함
	return tree[node] = (init(start, mid, node * 2) * init(mid+1, end, node * 2 + 1))% MOD; // {0, 10, 1} -> {0, 5, 2} + {6,10,3} 
}

void  update(int start, int end, int node, int idx, int dif, int dif2) { // double로 하면 손실 값 생길것 같다. 
	//범위 밖
	if (idx < start || end < idx) 
		return;

	if (start == end) {
		tree[node] = dif2;
		v[idx] = dif2;
		return;
	}

	//내려가면서 계속 갱신
	int mid = (start + end) / 2;
	update(start, mid, node * 2, idx, dif, dif2);
	update(mid + 1, end, node * 2 + 1, idx, dif, dif2);

	tree[node] = ((tree[node * 2] % MOD )* (tree[node * 2 + 1] % MOD)) % MOD;

}

//구간 곱 구하기
ll multi(int start, int end, int node, int left, int right) {
	//범위 안에 없음
	if (right < start || end < left)
		return 1;

	//범위 안
	if (left <= start && end <= right)
		return tree[node];

	//범위 걸치면
	int mid = (start + end) / 2;

	return (multi(start, mid, node * 2, left, right))% MOD * (multi(mid + 1, end, node * 2 + 1, left, right)%MOD)% MOD;
	
}
int main() {

	cin >> N >> M >> K;

	v.resize(N + 1);
	tree.resize(4 * N); // (N보다 조금 큰 값 (제곱수) )*2< N * 4

	for (int i = 0; i < N; i++)
		cin >> v[i];

	int cmd = 0, b = 0, c = 0;

	init(0, N - 1, 1);

	for (int i = 0; i < M + K; i++) {
		cin >> cmd >> b >> c;

		if (cmd == 1) {
			
			update(0, N - 1, 1, b - 1, v[b - 1], c);
			
			
		}
		else
			cout << multi(0, N - 1, 1, b - 1, c - 1) << "\n";
	}
	
}

코멘트

- 세그먼트 트리 문제였는데 덧셈하고 좀 다른 부분이 까다로웠던 것 같습니다.

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

import java.io.*;
import java.util.*;

/**
 * 22:05 시작!
 */
public class Main
{
    /**
     * 누적합?
     */
    static int MOD = 1_000_000_007;
    static long[] nums, tree;
	public static void main(String[] args) throws Exception {
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(bf.readLine());
	    StringBuilder answer = new StringBuilder();
	    
	    int n = Integer.parseInt(st.nextToken()); // 최대 100만
	    int m = Integer.parseInt(st.nextToken()); // 최대 1만
	    int k = Integer.parseInt(st.nextToken()); // 최대 1만
	    
	    nums = new long[n + 1];
	    for(int i = 1; i <= n; ++i) {
	        nums[i] = Integer.parseInt(bf.readLine());
	    }
	    
	    tree = new long[n * 4];
	    initTree(1, n, 1);
	    
	    for(int i = 0; i < m + k; ++i) {
	        st = new StringTokenizer(bf.readLine());
	        int cmd = Integer.parseInt(st.nextToken());
	        int arg1 = Integer.parseInt(st.nextToken());
	        int arg2 = Integer.parseInt(st.nextToken());
	        
	        if(cmd == 1) {
				update(1, n, 1, arg1, arg2);
	            continue;
	        }
	        
	        // cmd == 2
	        answer.append(multiply(1, n, 1, arg1, arg2) % MOD)
	            .append("\n");
	    }
	    
	    System.out.println(answer.toString());
	}
	
	static long initTree(int start, int end, int node) {
		if(start == end) return tree[node] = nums[start];
		
		int mid = (start + end) / 2;
		return tree[node] = (initTree(start, mid, node * 2) * initTree(mid + 1, end, node * 2 + 1)) % MOD;
	}
	
	static long update(int start, int end, int node, int idx, int value) {
		if(end < idx || idx < start) return tree[node];
		if(start == end) return tree[node] = value;
		
		int mid = (start + end) / 2;
		return tree[node] = (update(start, mid, node * 2, idx, value) * update(mid + 1, end, node * 2 + 1, idx, value)) % MOD;
	}
	
	static long multiply(int start, int end, int node, int left, int right) {
		if(end < left || right < start) return 1;
		if(left <= start && end <= right) return tree[node];
		
		int mid = (start + end) / 2;
		return (multiply(start, mid, node * 2, left, right)* multiply(mid + 1, end, node * 2 + 1, left, right)) % MOD;
	}
}

코멘트

-