11505 - 구간 곱 구하기
본문
어떤 $N$개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 $1, 2, 3, 4, 5$ 라는 수가 있고, 3번째 수를 $6$으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 $240$을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 $2$로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 $48$이 될 것이다.
입력
첫째 줄에 수의 개수 $N(1 \leq N \leq 1\,000\,000)$과 $M(1 \leq M \leq 10\,000)$, $K(1 \leq K \leq 10\,000)$ 가 주어진다. $M$은 수의 변경이 일어나는 횟수이고, $K$는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 $N+1$번째 줄까지 $N$개의 수가 주어진다. 그리고 $N+2$번째 줄부터 $N+M+K+1$ 번째 줄까지 세 개의 정수 $a,b,c$가 주어지는데, $a$가 1인 경우 $b$번째 수를 $c$로 바꾸고 $a$가 2인 경우에는 $b$부터 $c$까지의 곱을 구하여 출력하면 된다.
입력으로 주어지는 모든 수는 $0$보다 크거나 같고, $1\,000\,000$보다 작거나 같은 정수이다.
출력
첫째 줄부터 $K$줄에 걸쳐 구한 구간의 곱을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 256MB |
풀이
세그먼트 트리의 기본형 문제다. 문제에서 원하는 조건이 아래 2개밖에 없다.
- 특정 숫자를 바꾸기
- 특정 구간의 곱을 출력하기
위 2개 연산은 세그먼트 트리의 기본형에서도 구현했던 연산들이다. 따라서 세그먼트 트리 기본형을 가져오면 문제를 바로 해결할 수 있다.
문제가 있다면 숫자의 입력으로 $0$이 들어올 수 있는 것, 숫자의 범위가 너무 커지기 때문에 mod를 취해야한다는 것. 이렇게 2가지 문제점이 있다. 하나씩 해결해보자.
일단 mod를 취해야하는 것은 자주 사용하는 기술이다. 숫자의 범위가 크므로 일단 long long형을 사용해야할 것이다. 그런데, 우리는 특정 숫자를 바꿀 것이기 때문에 기존에 구해놨던 구간 곱에서 기존의 수를 나눠주고 새로운 수를 곱해주는 것으로 갱신할 수 있다. 근데 이렇게 하면 계산이 안된다. 구간곱에 모듈러 연산이 적용되어있기 때문. 그래서 그냥 나눠버리면 안되고, 나누는 수의 inverse를 계산하여 구하는 것이 일반적이다.
가장 큰 문제점이, 입력으로 주어질 수 있는 숫자들 중에서 $0$이 있다는 점이다. $0$이 들어옴으로써 구간의 전체 값이 $0$이 되기도 하고, 기존에 $0$이었던 부분이 다른 숫자로 변경되면서 구간 값이 $0$이 아니게 될 수도 있다. 문제는 그때마다 구간에 $0$을 곱하거나 inverse($0$)을 계산해주어야한다는 것. $0$을 곱하는 것은 문제가 되지 않지만, inverse($0$)은 문제가 된다. 저것을 만족하는 값이 없기 때문.
결론적으로, 세그먼트 트리의 기본형에서 update함수에서 사용하던 diff 방법은 사용할 수 없다는 결론이 난다. 그래서, 특정 수가 변경될 때 변경된 값을 그 노드에서 계산하지말고, 리프노드부터 값을 다시 계산해서 위로 올리는 bottom-up 방법을 사용하도록 한다.
- 참고 알고리즘 : 세그먼트 트리
코드
사용 언어 : C
최종 수정일 : 2023 / 3 / 28
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
#include <stdio.h>
typedef long long ll;
#define MAX_IDX (int)(1e6)
const int MOD = (int)(1e9 + 7);
int arr[MAX_IDX];
int n, m, k;
ll tree[MAX_IDX * 4];
const int ROOT = 1;
ll init(int node, int s, int e) {
if (s == e) {
return tree[node] = arr[s];
} else {
return tree[node] = (init(node * 2, s, (s + e) / 2) * init(node * 2 + 1, (s + e) / 2 + 1, e)) % MOD;
}
}
void update(int node, int s, int e, int t, int nv) {
if (t < s || t > e) {
return;
} else if (s == e) {
tree[node] = nv;
return;
}
update(node * 2, s, (s + e) / 2, t, nv);
update(node * 2 + 1, (s + e) / 2 + 1, e, t, nv);
tree[node] = tree[node * 2] * tree[node * 2 + 1] % MOD;
return;
}
ll query(int node, int s, int e, int l, int r) {
if (l > e || r < s) {
return 1;
}
if (l <= s && e <= r) {
return tree[node];
}
return query(node * 2, s, (s + e) / 2, l, r) * query(node * 2 + 1, (s + e) / 2 + 1, e, l, r) % MOD;
}
int main() {
scanf("%d %d %d", &n, &m, &k);
for (int i = 0; i < n; ++i) {
scanf("%d", arr + i);
}
init(ROOT, 0, n - 1);
for (int i = 0; i < m + k; ++i) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
switch (a) {
case 1: {
update(ROOT, 0, n - 1, b - 1, c);
arr[b - 1] = c;
break;
}
case 2: {
printf("%lld\n", query(ROOT, 0, n - 1, b - 1, c - 1) % MOD);
}
}
}
return 0;
}