Post List

[BOJ] 구간 곱 구하기

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

이 문제 또한 세그먼트 트리로 구하면 되는 문제 입니다.

주의할 점은, MOD할 때 질의부분과 업데이트 부분, 그리고 init 부분 모두 해줘야 한다는 점이며, 범위가 아닌 부분을 MUL할 때 0을 반환하면 안되고, 1을 반환해 주어야 한다는 점 입니다.

소스코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <queue>
typedef long long ll;
using namespace std;
int n, m, k;
ll MOD = 1000000007;
ll num[1000001]{ 1, };
ll tree[1000001 * 4]{ 1, };
ll Init(int node, int start, int end) {
    if (start == end) {
        return tree[node] = num[start];
    }
    int mid = (start + end/ 2;
    
    return tree[node] = (Init(2 * node, start, mid) * Init(2 * node + 1, mid + 1end)) % MOD;
}
ll update(int index, int newValue, int node, int start, int end) {
    if (index < start || end < index) {
        return tree[node];
    }
    if (start == end)
        return tree[node] = newValue;
    int mid = (start + end/ 2;
    return tree[node] = (update(index, newValue, node * 2, start, mid) * update(index, newValue, node * 2 + 1, mid + 1end)) % MOD;
}
ll Sum(int left, int right, int node, int start, int end) {
    if (left <= start && end <= right) {
        
        return tree[node];
    }
    if (right < start || end < left) {
        return 1;
    }
    int mid = (start + end/ 2;
    return (Sum(left, right, node * 2, start, mid) * Sum(left, right, node * 2 + 1, mid + 1end)) % MOD;
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }
    // Initiating of seg tree.
    Init(11, n);
    for (int i = 1; i <= m + k; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        if (a == 1) {
            update(b, c, 11, n);
        }
        else {
            cout << Sum(b, c, 11, n) << '\n';
        }
    }
}
cs

댓글