백준(BOJ) 11505 구간 곱 구하기 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/11505

11505번: 구간 곱 구하기

문제 풀이에 이용된 알고리즘: 세그먼트 트리

 

지난 포스팅 중 (https://jinho9610.tistory.com/23)을 먼저 읽고 오길 바란다.

백준(BOJ) 11659 구간 합 구하기 C++ 풀이

 

이번에는 구간합이 아닌 구간"곱"을 구하는 문제이다.

 

동일하게 세그먼트 트리를 이용한다면, 구간에 대한 연산을 해서 트리를 구성하고 쿼리를 날리는 것은 크게 차이가 없다고 자명히 생각할 수 있을 것이다.

 

차이는 겨우 한 글자, "합"과 "곱"이다.

 

실제로 이 차이에 의해서 발생할 수 있는 부분에 대해서만 수정을 진행하면 된다.

 

1. "합"에서는 서로 다른 구간의 결과를 +하는 방법으로 트리 구성이나 쿼리가 진행된다.

   "곱"에서는 당연히 *가 이용되어야 한다.

 

2. "합"에서 특정 구간의 합을 파악하기 위해서 쿼리 함수를 호출했을 때, 관심있는 구간과 전혀 상관없는 구간에 대한 합 정보를 가지고 있는 노드를 만나면 0을 return한다. 하지만 "곱"에서는 이런 0이 발생할 경우, 모든 구간곱이 0이 된다. 따라서 1을 return해야한다.

 

3. 이번 문제에서는 숫자의 변경이 발생하므로 update 함수를 구현해야 한다.

 

4. 곱의 경우 굉장히 큰 수가 발생할 수 있으므로 모듈러 연산을 꼭 중간 중간 수행해야 정답 처리가 된다.(특히 세그먼트 트리에서는 int의 범위를 벗어나는 숫자나 답이 발생하는 경우가 많으므로, 큰 고민 없이 세그 트리와 관련된 함수에 이용되는 자료형을 long long 타입으로 선언하자.)

 

/* BOJ 11505 구간곱구하기 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int n, m, k;
ll arr[1000001];
vector<ll> tree;
 
ll make_tree(int node, int start, int end)
{
    if (start == end) return tree[node] = arr[start];
 
    int mid = (start + end) / 2;
    return tree[node] = (make_tree(node * 2, start, mid) * make_tree(node * 2 + 1, mid + 1, end)) % 1000000007;
}
 
ll query(int node, int start, int end, int left, int right)
{
    if (left > end || start > right) return 1;
 
    if (left <= start && end <= right) return tree[node];
 
    int mid = (start + end) / 2;
    return (query(node * 2, start, mid, left, right) * query(node * 2 + 1, mid + 1, end, left, right))%1000000007;
}
 
void update(int node, int start, int end, int idx, ll value)
{
    if (idx < start || end < idx) return;
 
    if (start == end)
    {
        tree[node] = value;
        return;
    }
 
    int mid = (start + end) / 2;
    update(node * 2, start, mid, idx, value);
    update(node * 2 + 1, mid + 1, end, idx, value);
    tree[node] = (tree[node * 2] * tree[node * 2 + 1]) % 1000000007;
}
 
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    tree.resize(n * 4);
 
    make_tree(1, 1, n);
 
    for (int i = 0; i < m + k; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
            update(1, 1, n, b, c);
        else
            cout << query(1, 1, n, b, c) << endl;
    }
 
    return 0;
}