문제
11505번: 구간 곱 구하기 (acmicpc.net)
풀이
배열이 주어지고 배열의 구간의 대한 값을 물어보는 문제입니다. 값을 가져오는 것 말고도 변경하는 작업도 해야하기 때문에 구간합과 같은 배열을 이용하기 보단, 세그먼트 트리를 이용해야 합니다.
세그먼트 트리의 구현에 대한 문제이므로 세그먼트 트리를 먼저 공부한 뒤 푸는것이 좋습니다.
이 문제에서 주의할 점은 구간의 곱을 구하기 때문에 구간을 벗어나는 노드인 경우 0이 아닌 1을 리턴해야 합니다.
곱셈이기 때문에 0을 리턴해버리면 이후 모든 곱셈연산이 0을 결과로 가지게됩니다.
int getMul(pair<int, int> range, int idx, int start, int end)
{
if (end < range.first || range.second < start)
return 1;
if (range.first <= start && end <= range.second)
return tree[idx];
int mid = (start + end) / 2;
return (uint64_t)getMul(range, idx*2 + 1, start, mid) * getMul(range, idx*2 + 2, mid+1, end) % MOD;
}
각 노드의 값은 1,000,000,007로 나눈 나머지 값을 저장하므로 32비트로 표현이 가능합니다.
하지만 부모 노드의 값을 계산하기 위해 두 자식 노드의 값을 곱할때 오버플로우가 발생해버리기 때문에 이에 대한 처리가 필요합니다.
간단하게 노드의 자료형 크기를 64비트로 선언하여 곱할때의 오버플로우를 해결할 수 있고,
또는 곱셈 연산을 할 때 형변환을 해주어 오버플로우를 해결할 수 있습니다.
return tree[idx] = (uint64_t)init() * init() % MOD;
코드
#include <iostream>
#include <vector>
#include <cmath>
#define MOD 1000000007
using namespace std;
int n, m, k;
int height;
int treeSize;
vector<uint64_t> arr;
vector<uint64_t> tree;
uint64_t init(int idx, int start, int end)
{
if (start == end)
return tree[idx] = arr[start];
int mid = (start + end) / 2;
tree[idx] = init(idx*2 + 1, start, mid) * init(idx*2 + 2, mid + 1, end) % MOD;
return tree[idx] ;
}
uint64_t getMul(pair<int, int> range, int idx, int start, int end)
{
if (end < range.first || range.second < start)
return 1;
if (range.first <= start && end <= range.second)
return tree[idx];
int mid = (start + end) / 2;
return getMul(range, idx*2 + 1, start, mid) * getMul(range, idx*2 + 2, mid+1, end) % MOD;
}
uint64_t update(int num, int target, int idx, int start, int end)
{
// if (start == end && target == start)
// return tree[idx] = num;
if (target < start || end < target) // 반드시 이 조건 먼저 확인
return tree[idx];
if (start == end)
return tree[idx] = num;
int mid = (start + end) / 2;
return tree[idx] = update(num, target, idx*2 + 1, start, mid) * update(num, target, idx*2 + 2, mid+1, end) % MOD;
}
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> m >> k;
arr.resize(n);
height = ceil(log2(n));
treeSize = (1 << (height+1) )-1;
tree.resize(treeSize, 0);
for (int i=0; i<n; ++i)
{
cin >> arr[i];
}
init(0, 0, n-1);
for (int i=0; i< m+k; ++i)
{
int a, b, c;
cin >> a >> b >> c;
if (a == 1)
{
update(c, b-1, 0, 0, n-1);
}
else
{
cout << getMul({b-1, c-1}, 0, 0, n-1) << "\n";
}
}
return 0;
}
'백준 > 자료 구조' 카테고리의 다른 글
[백준] 17435 합성함수와 쿼리 (C++) (1) | 2023.11.11 |
---|---|
[백준] 1655 가운데를 말해요 (C++) (0) | 2023.10.18 |