[11505번] 구간 곱 구하기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리(Segment Tree) :: http://www.crocus.co.kr/648

2. 구간 트리의 응용

구간 합과 다른것이 딱히 없고 곱에 대한 정의와 그것을 이용하여 구간 합에서 구간 곱으로 변형시키는 문제이다.

주석을 통해 구간 곱에 필요한 세그먼트 트리 함수들의 설명을 적어두었다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <math.h>
 
#define MOD 1000000007
 
using namespace std;
 
typedef long long ll;
 
ll val;
 
ll init(vector<ll> &arr, vector<ll> &tree, int node, int start, int end)
{
    // start == end면 리프 노드이다.
    if (start == end)
        return tree[node] = arr[start];
 
    // 각 노드의 자식 노드에서 타고 올라온 return 값을 곱해주어 자신의 노드에 값을 넣는다.
    else
        return tree[node] = ((init(arr, tree, node * 2, start, (start + end) / 2) % MOD) * (init(arr, tree, node * 2 + 1, (start + end) / 2 + 1, end) % MOD)) % MOD;
}
 
ll update(vector<ll> &tree, int node, int start, int end, int index)
{
    // start와 end 구간 사이에 index가 아니면 갱신없이 현재 노드를 반환해준다. 
    if (!(start <= index && index <= end))
        return tree[node];
 
    // 리프 노드 업데이트
    if (start == end)
        return tree[node] = val;
 
    return tree[node] = (update(tree, node * 2, start, (start + end) / 2, index) * update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index))%MOD;
}
 
ll mul(vector<ll> &tree, int node, int start, int end, int left, int right)
{
    // 현재 구하고자 하는 범위의 값이 아닌경우 구간 곱이기에 1을 return
    if (left > end || right < start)
        return 1;
 
    // left와 right가 start와 end를 포함하는 경우 현재 노드를 반환
    if (left <= start && end <= right)
        return tree[node];
 
    return ( mul(tree, node * 2, start, (start + end) / 2, left, right) * mul(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right) )% MOD;
}
int main()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
 
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h + 1));
 
    vector<ll> arr(n);
    vector<ll> tree(tree_size);
 
    for (int i = 0; i < n; i++)
 
        scanf("%lld", &arr[i]);
 
    init(arr, tree, 1, 0, n - 1);
 
    m += k;
 
    while (m--)
    {
        int get;
        scanf("%d", &get);
 
        // 구간을 갱신
        if (get == 1)
        {
            int pos;
 
            scanf("%d %lld", &pos, &val);
            update(tree, 1, 0, n - 1, pos - 1);
        }
 
        // 구간 곱을 출력
        else if (get == 2)
        {
            int left, right;
            scanf("%d %d", &left, &right);
            printf("%lld\n", mul(tree, 1, 0, n - 1, left - 1, right - 1)%MOD);
        }
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>