https://www.acmicpc.net/problem/11505
11505번: 구간 곱 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
이 문제에서 주의해야하는 점
1. 입력으로 주어진 수가 0보다 크거나 같다.
업데이트할 때 기존의 값이 0일 때를 고려해야 한다.
구간 합 처럼 아래에서 위로 올라간다
0 * 변경된 데이터이므로 업데이트가 되지 않는다.
// 값을 바꾸고 부모 = 왼쪽 노드 * 오른쪽 노드
while (idx > 1)
{
idx = idx / 2;
tree[idx] = tree[idx * 2] % mod * tree[idx * 2 + 1] % mod;
}
2. 나머지 연산
(A * B) & C = (A % C) * (B % C) % C
3. 구간곱이므로
초기화 할 때 1로 채워준다.
fill(tree.begin(), tree.end(), 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<long> tree;
int mod = 1000000007;
// 구간 곱 트리 초기화
void setTree(int i)
{
while (i != 1)
{
tree[i / 2] = tree[i / 2] * tree[i] % mod;
i--;
}
}
// 트리 값 업데이트
void updateVal(int idx, long val)
{
tree[idx] = val;
// 값을 바꾸고 부모 = 왼쪽 노드 * 오른쪽 노드
while (idx > 1)
{
idx = idx / 2;
tree[idx] = tree[idx * 2] % mod * tree[idx * 2 + 1] % mod;
}
}
// 곱셈이 발생할 때마다 mod 연산
long getMul(int s, int e)
{
long partMul = 1;
while (s <= e)
{
if (s % 2 == 1)
{
partMul = partMul * tree[s] % mod;
s++;
}
if (e % 2 == 0)
{
partMul = partMul * tree[e] % mod;
e--;
}
s = s / 2;
e = e / 2;
}
return partMul;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
int treeHeight = 0;
int Length = n;
while (Length != 0)
{
Length /= 2;
treeHeight++;
}
int treeSize = int(pow(2, treeHeight + 1));
int leftNodeStartIndex = treeSize / 2 - 1;
tree.resize(treeSize + 1);
//구간 곱이므로 초기값을 1로 설정해야함!
fill(tree.begin(), tree.end(), 1);
// 데이터를 리프 노드에 입력받기
for (int i = leftNodeStartIndex + 1; i <= leftNodeStartIndex + n; i++)
{
cin >> tree[i];
}
setTree(treeSize - 1);
// m은 변경 횟수, k는 구간곱 구하는 횟수
for (int i = 0; i < m + k; i++)
{
long a, s, e;
cin >> a >> s >> e;
if (a == 1)
updateVal(leftNodeStartIndex + s, e);
else if (a == 2)
{
s = s + leftNodeStartIndex;
e = e + leftNodeStartIndex;
cout << getMul(s, e) << '\n';
}
}
}
|
cs |