[BOJ] 백준 11505 구간 곱 구하기

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

 Input 

5 2 2

1

2

3

4

5

1 3 6

2 2 5

1 5 2

2 3 5

　 

 Output 

240

48

배열의 특정 구간이 자주 변경되므로 세그먼트 트리(Segment Tree)를 이용합니다.

 

곱셈의 특성상 구간의 곱을 가지고 있으면 무수히 커질 수 있기 때문에 문제에서 모듈러연산을 요구합니다.

최종 결과에만 모듈러연산을 해준다면 노드가 가지고 있는 값이 Overflow 될 수 있으므로

노드가 가진 값을 갱신할 때도 % 연산 처리 합니다.

---

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 1000000007
#define LM 1000000
typedef long long ll;
using namespace std;
ll val, a, b;
ll tree[4 * LM];
 
ll update(ll idx, ll val, ll node, ll start, ll end) {
    if (end < idx || idx < start)
        return tree[node];
    if (start == end) // 단말 노드(Leaf Node)인 경우
        return tree[node] = val;
 
    ll mid = (start + end) >> 1;
    return tree[node] = (update(idx, val, node * 2, start, mid) 
        * update(idx, val, node * 2 + 1, mid + 1, end)) % MOD;
}
 
ll query(ll node, ll start, ll end, ll qLeft, ll qRight) {
    if (end < qLeft || qRight < start)
        return 1;
    if (qLeft <= start && end <= qRight)
        return tree[node];
 
    ll mid = (start + end) >> 1;
    return (query(node * 2, start, mid, qLeft, qRight) 
        * query(node * 2 + 1, mid + 1, end, qLeft, qRight)) % MOD;
}
 
int main() {
    int i, N, M, K, cmd;
    scanf("%d %d %d", &N, &M, &K);
 
    for (i = 1; i <= N; i++) {
        scanf("%lld", &val);
        update(i, val, 1, 1, N);
    }
    for (i = 0; i < M + K; i++) {
        scanf("%d %lld %lld", &cmd, &a, &b);
        if (cmd == 1)
            update(a, b, 1, 1, N);
        else 
            printf("%lld\n", query(1, 1, N, a, b));
    }
}