BOJ)11505 구간 곱 구하기

문제:icpc.me/11505

구간에 대한 곱을 출력하는 문제이다. 값의 갱신이 빈번하게 일어나기 때문에 세그먼트 트리를 이용해주면 된다.

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

이때 단순히 답에만 모듈러연산을 해준다면 노드가 가지고 있는 값이 오버플로우 될 수 있으므로 우리는 노드가 가진 값들을 업데이트 할 때 와 쿼리를 처리할 때도 모듈러연산을 해줘야 한다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 1000000007
#define MAX_N 1000000
typedef long long ll;
using namespace std;
ll n, m, k, t, x, y, z;
ll seg[4*MAX_N];
ll update(ll pos, ll val, ll node, ll x, ll y){
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    ll mid = (x + y) >> 1;
    return seg[node] = (update(pos, val, node * 2, x, mid)*update(pos, val, node * 2 + 1, mid + 1, y)) % MOD;
}
ll query(ll lo, ll hi, ll node, ll x, ll y){
    if (y < lo || hi < x)
        return 1;
    if (lo <= x&&y <= hi)
        return seg[node];
    ll mid = (x + y) >> 1;
    return (query(lo, hi, node * 2, x, mid)*query(lo, hi, node * 2 + 1, mid + 1, y)) % MOD;
}
int main(){
    scanf("%lld%lld%lld", &n, &m, &k);
    for (ll i = 1; i <= n; i++){
        scanf("%lld", &t);
        update(i, t, 1, 1, n);
    }
    for (ll i = 0; i < m + k; i++){
        scanf("%lld%lld%lld", &x, &y, &z);
        if (x == 1)
            update(y, z, 1, 1, n);
        else
            printf("%lld\n", query(y, z, 1, 1, n));
    }
    return 0;
}