[백준 11505] 구간 곱 구하기 (C++)

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

11505번: 구간 곱 구하기

1. 주의할 점

- 세그먼트 트리에 대해 알고 있어야 한다

- MOD 연산, 0으로 나누기를 유의해야 한다

 

2. 구현

- Num의 크기만큼 Arr[] 배열에 초기값을 입력 받는다

- Num을 통해 Height를 계산한 이후, Tree[] 배열을 동적할당한다

- Init() 함수를 통해 Tree[] 배열을 갱신한다

- 값이 변경되는 경우, Arr[] 배열의 값을 변환하고 Update() 함수를 통해 Tree값을 변환한다. 이때, MOD 연산에 의해 생성된 나머지를 통해 Update를 시도할 경우, 다른 값을 도출할 수 있기 때문에 Tree[] 배열의 LeafNode부터 갱신해야 한다

- 구간곱을 구할 경우, Mul() 함수를 통해 구간곱을 구하도록 한다

#define MOD 1000000007
#include <iostream>
#include <cmath>
using namespace std;
long long arr[1000001];
long long *tree;

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

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

long long update(int node, int start, int end, int idx, long long val){
    if(idx>end || idx<start) return tree[node];
    if(start==end) return tree[node]=val;
    int mid = start + (end-start)/2;
    return tree[node] = (update(2*node,start,mid,idx,val)*update(2*node+1,mid+1,end,idx,val))%MOD;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,m,k,height,a;
    long long b,c,big,small;
    cin>>num>>m>>k;
    height = ceil(log2(num));
    tree = new long long[1<<(height+1)];
    for(int i=0;i<num;i++)
        cin>>arr[i];
    
    init(1,0,num-1);
    for(int i=0;i<m+k;i++){
        cin>>a>>b>>c;
        if(a==1){   //b번째 수->c
            arr[b-1]=c;
            update(1,0,num-1,b-1,c);
        }
        else{       //b~c 구간 곱
            big = b>c ? b:c;
            small = b>c ? c:b;
            cout << mul(1,0,num-1,small-1,big-1)<<'\n';
        }
    }
    return 0;
}