[BOJ 11505 // C++] 구간 곱 구하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11505번 분제인 구간 곱 구하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11505

11505번: 구간 곱 구하기

이 문제는 구간 합을 구하는 세그먼트 트리(segment tree)랑 마찬가지로 구현을 하면 되나, 값을 갱신할 때 나머지 연산과 곱셈 연산은 순서를 자유롭게 바꿀 수 없으므로 이 점에 유의하여 구현해야 한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin; using std::cout;
typedef long long ll;

ll arr[1000001];
ll segtree[2097153];

ll initseg(int L, int R, int sIdx) {
    if (L == R) segtree[sIdx] = arr[L];
    else segtree[sIdx] = initseg(L, (L + R) / 2, sIdx * 2) * initseg((L + R) / 2 + 1, R, sIdx * 2 + 1) % 1000000007;
    return segtree[sIdx];
}

ll update(int L, int R, int qIdx, int sIdx, ll val) {
    if (L == R && L == qIdx) segtree[sIdx] = val;
    else if (L<=qIdx && qIdx <= R) segtree[sIdx] = update(L, (L + R) / 2, qIdx, sIdx * 2, val) * update((L+R)/2+1,R,qIdx,sIdx*2+1,val) % 1000000007;
    return segtree[sIdx];
}

ll rmultq(int L, int R, int qL, int qR, int sIdx) {
    if (qL <= L && R <= qR) return segtree[sIdx];
    if (R < qL || qR < L) return 1;
    else return rmultq(L, (L + R) / 2, qL, qR, sIdx * 2) * rmultq((L + R) / 2 + 1, R, qL, qR, sIdx * 2 + 1) % 1000000007;
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M, K; cin >> N >> M >> K;
    for (int i = 1;i <= N;i++) {
        ll x; cin >> x;
        arr[i] = x;
    }
    initseg(1, N, 1);
    for (int i = 0;i < M + K;i++) {
        ll q, a, b; cin >> q >> a >> b;
        if (q == 1) {
            update(1, N, a, 1, b);
        }
        else cout << rmultq(1, N, a, b, 1) << '\n';
    }
    return 0;
}