BOJ 11505 : 구간 곱 구하기

우리는 세그먼트 트리를 이용하여 쉽게 구할 수 있다.

 

구간 합 세그트리를 구현 할 줄 안다면 쉽게 구현이 가능하다.

 

#include <bits/stdc++.h>
#define sanic ios_base::sync_with_stdio(0);
#define MEM 4000004
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
ll n,m,k;
ll tree[MEM], a[MEM];
ll init(int idx, int l, int r){
    if(l==r)
       return tree[idx] = a[l];
    int mid=(l+r)/2;
    return tree[idx] = ((init(idx*2, l, mid)%MOD)*(init(idx*2+1, mid+1, r)%MOD))%MOD;
}
ll update(int nd, int idx, ll ch, int l, int r){
    if(!(l<=idx && idx<=r))
        return tree[nd];
    if(l==r)
        return tree[nd] = ch;
    int mid=(l+r)/2;
    return tree[nd] = ((update(nd*2,idx,ch,l,mid)%MOD)*(update(nd*2+1,idx,ch,mid+1,r)%MOD))%MOD;
}
ll pii(int idx, int s, int e, int l, int r){
    if(e<l || r<s)
        return 1;
    else if(l<=s && e<=r)
        return tree[idx];
    int mid=(s+e)/2;
    return (pii(idx*2,s,mid,l,r)*pii(idx*2+1,mid+1,e,l,r))%MOD;
}
main()
{
    sanic; cin.tie(0);
    cin >> n >> m >> k;
	for(int i=1; i<=n; i++)
        cin >> a[i];
    init(1, 1, n);
    m += k;
    while(m--){
        ll q,q1,q2;
        cin >> q >> q1 >> q2;
        if(q==1)
            update(1, q1, q2, 1, n);
        else
            cout << pii(1,1,n,q1,q2) << '\n';
    }
}