백준 11505 구간 곱 구하기

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

11505번: 구간 곱 구하기

단순히 구간 합 세그먼트 트리에서 구간 곱 세그먼트트리로 바꾸는 문제입니다

 

https://wantchicken.tistory.com/46

세그먼트 트리의 개념 - c++

포스팅을 보고 오셨다면 어렵지 않으실 것입니다.

 

#include <iostream>
#include <math.h>
#define mod        1000000007
#define fastio() ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
using namespace std;
typedef long long ll;
ll n, m, k, from;
ll arr[10000000];
void update(ll location, ll v) {
    ll idx = location + from - 1;
    arr[idx] = v;
    for (ll i = idx / 2; i >= 1; i /= 2) {
        arr[i] = (arr[i * 2] * arr[i * 2 + 1]) % mod;
    }
}
ll sum(ll l, ll r, ll idx = 1, ll L = 1, ll R = from) {
    if (l > R or r < L) return 1;
    else if (l <= L and r >= R) return arr[idx];
    ll m = (L + R) / 2;
    return (sum(l, r, idx * 2, L, m) * sum(l, r, idx * 2 + 1, m + 1, R)) % mod;
}
 
int main() {
    fastio();
    cin >> n >> m >> k;
    from = ((n & (n - 1)) == 0) ? pow(2, (int)log2(n)) : pow(2, (int)log2(n) + 1);
    for (int i = 1; i < from + n; i++) arr[i] = 1;
    for (ll i = from; i < from + n; i++) cin >> arr[i];
    for (ll i = from - 1; i >= 1; --i) arr[i] = (arr[i * 2] * arr[i * 2 + 1]) % mod;
    for (ll i = 0; i < m + k; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        if (a == 1) {
            update(b, c);
        }
        else {
            cout << sum(b, c) << "\n";
        }
    }
}