[ 백준 11505 ] 구간 곱 구하기 (C++)

백준의 구간 곱 구하기(11505) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

세그먼트 트리(Segment Tree)를 이용해서 접근할 수 있는 문제이다.

아직 세그먼트 트리에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 세그먼트 트리(Segment Tree) 알아보기(Click) ]

위의 설명된 글은 '구간 합 구하기'에 초점이 맞춰진 설명이다.

이 문제는 달리 구간의 곱을 구해야 하기 때문에 노드들이 갖는 결과값이 노드가 포함하는 구간의 합이 아닌 곱으로 연산 결과를 바꿔주기만 하면 된다. 또한, 업데이트를 할 때, 업데이트한 Index를 포함하고 있는 구간을 가진 노드라면 해당 값만큼 ++시켜주면

되는데 이 문제는 곱하기 이기 때문에 결과값을 해당 Index를 포함하고 있다고 하더라도 쉽게 바꿀 수 없다.

따라서, Update도 리프노드가 될 때 까지 왼쪽자식과 오른쪽 자식을 나누어서 업데이트 시켜주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MODULER 1000000007
#define MAX 1000010
typedef long long ll;
using namespace std;
 
int N, M, K;
ll Array[MAX];
vector<ll> SegmentTree;
vector<pair<pair<ll, ll>, ll>> Cmd;
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) cin >> Array[i];
    for (int i = 0; i < M + K; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Cmd.push_back(make_pair(make_pair(a, b), c));
    }
}
 
ll Make_SegmentTree(int Node, int Start, int End)
{
    if (Start == End) return SegmentTree[Node] = Array[Start] % MODULER;
    
    int Mid = (Start + End) / 2;
    ll Left_Result = Make_SegmentTree(Node * 2, Start, Mid);
    ll Right_Result = Make_SegmentTree(Node * 2 + 1, Mid + 1, End);
    SegmentTree[Node] = (Left_Result * Right_Result) % MODULER;
    return SegmentTree[Node];
}
 
ll Update(int Node, int Start, int End, int Idx, ll Num)
{
    if (Idx < Start || End < Idx) return SegmentTree[Node];
    if (Start == End) return SegmentTree[Node] = Num;
 
    int Mid = (Start + End) / 2;
    ll Left_Result = Update(Node * 2, Start, Mid, Idx, Num);
    ll Right_Result = Update(Node * 2 + 1, Mid + 1, End, Idx, Num);
    ll Result = (Left_Result * Right_Result) % MODULER;
 
    return SegmentTree[Node] = Result;
}
 
ll Multiple(int Node, int Start, int End, int Left, int Right)
{
    if (Left > End || Right < Start) return 1;
    if (Left <= Start && End <= Right) return SegmentTree[Node];
    
    int Mid = (Start + End) / 2;
    ll Left_Result = Multiple(Node * 2, Start, Mid, Left, Right);
    ll Right_Result = Multiple(Node * 2 + 1, Mid + 1, End, Left, Right);
    return (Left_Result * Right_Result) % MODULER;
}
 
void Solution()
{
    int Tree_Height = (int)ceil(log2(N));
    int Tree_Size = (1 << (Tree_Height + 1));
    SegmentTree.resize(Tree_Size);
    Make_SegmentTree(1, 0, N - 1);
 
    for (int i = 0; i < Cmd.size(); i++)
    {
        int Command = Cmd[i].first.first;
        
        if (Command == 1)
        {
            int Idx = Cmd[i].first.second - 1;
            ll Num = Cmd[i].second;
            Update(1, 0, N - 1, Idx, Num);
        }
        else
        {
            int Idx = Cmd[i].first.second - 1;
            int IIdx = Cmd[i].second - 1;
            cout << Multiple(1, 0, N - 1, Idx, IIdx) % MODULER << endl;
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}