링크 : https://www.acmicpc.net/problem/11505
이 문제 또한 세그먼트 트리로 구하면 되는 문제 입니다.
주의할 점은, MOD할 때 질의부분과 업데이트 부분, 그리고 init 부분 모두 해줘야 한다는 점이며, 범위가 아닌 부분을 MUL할 때 0을 반환하면 안되고, 1을 반환해 주어야 한다는 점 입니다.
소스코드 :
이 문제 또한 세그먼트 트리로 구하면 되는 문제 입니다.
주의할 점은, 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 + 1, end)) % 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 + 1, end)) % 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 + 1, end)) % 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(1, 1, n);
for (int i = 1; i <= m + k; i++) {
int a, b, c;
cin >> a >> b >> c;
if (a == 1) {
update(b, c, 1, 1, n);
}
else {
cout << Sum(b, c, 1, 1, n) << '\n';
}
}
}
| cs |
댓글
댓글 쓰기