링크
https://www.acmicpc.net/problem/11505
문제
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 48이 될 것이다.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 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로 나눈 나머지를 출력한다.
예제 입력 1
5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 5 2
2 3 5예제 출력 1
240
48예제 입력 2
5 2 2
1
2
3
4
5
1 3 0
2 2 5
1 3 6
2 2 5예제 출력 2
0
240아이디어 스케치
세그먼트 트리 자료구조를 이용하여 해결하는 문제로,
기존에 풀었던 부분합, 최댓값, 최솟값 세그먼트 트리에 이어 부분곱 세그먼트 트리 문제이다.
두 자식의 값의 곱을 부모 노드가 가지는 구조이며, 부분합 문제와 매우 유사하다.
N개의 수를 입력 받은 후 M번 수를 변경시키고, K번 구간의 곱을 구한다.
부분합 문제와 다른 부분을 설명하자면, 부분곱 문제는 리프 노드의 값이 변경될 경우에는 값이 변경된 노드와 같은 부모를 가진 자식노드를 곱한 값을 부모 노드의 값으로 갱신하는 작업을 루트 노드에 도달할 때 까지 반복해야 한다. 부분합 문제처럼 단순히 값의 변화량만 부모 노드를 타고 올라가면서 수정하는 것이 아닌 쌍을 이루는 자식 노드를 찾아 곱하면서 타고 올라가야한다.
값이 변경된 리프노드의 인덱스가 짝수인 경우에는 좌측 자식노드에 해당돠므로 우측 자식노드(좌측 자식 노드의 인덱스+1)와의 곱을 부모 노드의 값으로 갱신
값이 변경된 리프노드의 인덱스가 홀수인 경우에는 우측 자식노드에 해당되므로 좌측 자식노드(우측 자식 노드의 인덱스-1)와의 곱을 부모 노드의 값으로 갱신
위 과정을 루트 노드에 도달할 때 까지 수행하면 원하는 구간의 곱을 구할 수 있다.
값을 변경하는 함수 이외에 나머지 부분은 부분합 문제와 매우 유사하므로 설명을 생략한다.
전체 코드
#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define mod 1000000007
ll* tree;
int tree_size = 1;
void change(int a, int b);
ll partition_sum(int start, int end);
int main()
{
int N, M, K;
int command;
int a, b;
scanf("%d %d %d", &N, &M, &K);
// N보다 크면서 가장 가까운 2의 지수승 값을 구함
while (tree_size < N) {
tree_size *= 2;
}
tree = (ll*)calloc(tree_size * 2, sizeof(ll)); // 구한 2의 지수승 값에 2를 곱한 값을 크기로 하는 트리 생성
// 입력 받는 값들을 리프 노드에 저장
for (int i = tree_size; i < tree_size + N; i++)
scanf("%d", &tree[i]);
// 자식 노드의 값의 곱을 부모 노드에 저장
for (int i = tree_size - 1; i >= 1; i--)
tree[i] = (tree[2 * i] * tree[(i * 2) + 1])%mod;
int times = M + K; // M+K 횟수 만큼 연산
while (times--) {
scanf("%d %d %d", &command, &a, &b);
if (command == 1) change(a, b); // command가 1인 경우 값을 변경하는 함수 호출
else if (command == 2) printf("%d\n", partition_sum(a, b)); // command가 2인 경우 부분 곱을 구하는 함수 호출
}
// 메모리 할당 해제
free(tree);
return 0;
}
// 값을 변경하는 함수
void change(int a, int b)
{
int target_index = a + tree_size - 1; // 입력된 숫자의 순서를 트리의 인덱스로 변환
tree[target_index] = b; // 값을 변경하려는 인덱스의 값을 b로 설정
while (target_index / 2 >= 1) { // 루트 노드까지 수정
if (target_index % 2 == 0) { // target_index가 짝수인 경우에는 좌측 자식이므로 우측 자식과 곱한 값을 부모 노드에 저장
tree[target_index / 2] = (tree[target_index] * tree[target_index + 1])%mod;
target_index /= 2; // target_index를 부모 노드로 갱신
}
else { // target_index가 홀수인 경우에는 우측 자식이므로 좌측 자식과 곱한 값을 부모 노드에 저장
tree[target_index / 2] = (tree[target_index] * tree[target_index - 1]) % mod;
target_index /= 2;
}
}
}
// 부분합을 구하는 함수
ll partition_sum(int start, int end) {
ll sum = 1;
int start_index = start + tree_size - 1;
int end_index = end + tree_size - 1;
while (start_index <= end_index) { // start인덱스와 end인덱스가 뒤집히기 전까지 반복
if (start_index % 2 == 1) sum = (sum*tree[start_index])%mod; // start_index에 해당하는 노드가 우측 자식에 해당하는 경우에는 부모노드를 포함하지 않고 이 노드만 부분곱에 추가
if (end_index % 2 == 0) sum = (sum*tree[end_index])%mod; // end_index에 해당하는 노드가 좌측 자식에 해당하는 경우에는 부모 노드를 포함하지 않고 이 노드만 부분곱에 추가
start_index = (start_index + 1) / 2; // start_index를 부모 노드로 설정(+1을 하는 이유는 start_index가 우측 자식인 경우에는 현재 자식의 부모노드를 포함하지 않기 위함)
end_index = (end_index - 1) / 2; // end_index를 부모 노드로 설정(-1을 하는 이유는 end_index가 좌측 자식인 경우에는 현재 자식의 부모노드를 포함하지 않기 위함
}
return sum; // 결과 반환
}제출 결과
