(C++) - 백준(BOJ) 11505번 : 구간 곱 구하기

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

11505번: 구간 곱 구하기

기존 구간합을 구하는데 이용하는 segment tree를 약간 응용한 문제였습니다

 

 

 

📕 풀이방법

 

📔 입력 및 초기화

 n까지 수들을 입력받습니다. 이후 각 구간곱들을 tree라는 long long형 배열에 저장합니다.

 

 

📔 풀이과정

 1. a = 1일 때 : b-1이 가르키는 부분을 c로 갱신하며 구간곱들을 새로 바뀐 c에 맞춰 갱신 해줘야합니다. 하지만 기본 segment tree에서 차이만큼 나머지 구간들을 갱신했던 것과는 다르게 기존 차이만큼 곱할 수가 없습니다. 나눌때 발생하는 실수오차 때문입니다. 따라서 갱신할 필요 없는 구간은 놔두고 해당하는 구간들의 곱들을 다시 구해서 저장해야 합니다. 

 

 2. a = 2일 때 : b-1 ~ c-1까지의 구간곱들을 구해 반환해줍니다 

 

 

📔 정답출력

 a = 2일 때 b-1 ~ c - 1 구간곱을 출력해줍니다.

 

---

 

 

📕 Code

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll = long long;
ll n, m, k, num[1000001];
ll tree[4000001];

ll init(ll start, ll end, ll piv){
    if(start == end) return tree[piv] = num[start];
    ll mid = (start + end) / 2;
    return tree[piv] = init(start, mid, piv * 2) * init(mid + 1, end, piv * 2 + 1) % MOD;
}

ll mul(ll start, ll end, ll piv, ll left, ll right){
    if(left > end || right < start) return 1;
    if(left <= start && end <= right) return tree[piv];
    ll mid = (start + end) / 2;
    return mul(start, mid, piv * 2, left, right) * mul(mid + 1, end, piv * 2 + 1, left, right)  % MOD;
}

ll update(ll start, ll end, ll piv, ll idx, ll diff){
    if(idx < start || idx > end) return tree[piv];
    if(start == end ) return tree[piv] = diff;
    ll mid = (start + end ) / 2;

    return tree[piv] = 
    update(start, mid, piv * 2, idx, diff) *
    update(mid + 1, end, piv * 2 + 1, idx, diff) % MOD;
}

int main(){
    cin >> n >> m >> k;
    for(ll i = 0; i < n; i++) cin >> num[i];
    init(0,n-1,1);
    for(ll i = 0,a,b,c; i < m + k; i++){
        cin >> a >> b >> c;
        if(a == 1) update(0,n-1,1,b-1,c);
        else cout << mul(0,n-1,1,b-1,c-1) << '\n';
    }

}