11505번: 구간 곱 구하기

11505번: 구간 곱 구하기

사용 언어: C++

 

풀이

구간 합 구하기 문제와 유사. 구간의 곱을 구하는 것이므로 트리는 똑같이 만든다. 한 가지 다른 점은, 트리를 만들때 % MOD를 한다는 것인데, 어차피 마지막에 한번 Mod를 하나 중간 계속 Mod를 하나 결과는 같다. 그래서 Overflow가 안나게 매번 % MOD를 해준다는 것. Query에서도 곱을 하면서 % MOD를 해준다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MOD = 1'000'000'007;

constexpr int SZ = 1 << 20;
ll T[SZ << 1];

void Set(int x, ll v)
{
    x += SZ;
    T[x] = v;
    while (x /= 2)
    {
        T[x] = (T[x * 2] * T[x * 2 + 1]) % MOD;
    }
}

ll Query(int l, int r)
{
    ll res = 1;
    for (l += SZ, r += SZ; l <= r; l /= 2, r /= 2)
    {
        if (l % 2 == 1) res = (res * T[l++]) % MOD;
        if (r % 2 == 0) res = (res * T[r--]) % MOD;
    }
    return res;
}

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

    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i < N; i++)
    {
        ll num;
        cin >> num;
        Set(i, num);
    }

    for (int i = 0; i < M + K; i++)
    {
        int a, b;
        ll c;

        cin >> a >> b >> c;

        if (a == 1)
        {
            // b번째 수를 c로 변경
            Set(b - 1, c);
        }
        else if (a == 2)
        {
            cout << Query(b - 1, (int)c - 1) << '\n';
        }
    }

    return 0;
}