[백준/BOJ] gold1 - 11505번 구간 곱 구하기 (Python)

▶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로 나눈 나머지를 출력한다.

728x90

▶풀이

구간 합 구하기랑 거의 똑같은 문제이다.

더하는 것을 그냥 곱하기로만 바꿔줘도 정답이 나올 것이다.

2023.09.27 - [BOJ Code/Gold] - [백준/BOJ] gold1 - 2042번 구간 합 구하기 (Python)

[백준/BOJ] gold1 - 2042번 구간 합 구하기 (Python)

import sys
input = sys.stdin.readline


def init(start, end, index):
    if start == end:
        tree[index] = arr[start]
        return tree[index]
    
    mid = (start + end) // 2
    tree[index] = init(start, mid, index * 2) * init(mid + 1, end, index * 2 + 1) % 1000000007
    return tree[index]

def update(start, end, index, what, value):
    if what < start or what > end:
        return
    
    if start == end:
        tree[index] = value
    else:
        mid = (start + end) // 2
        update(start, mid, index * 2, what, value)
        update(mid + 1, end, index * 2 + 1, what, value)

        tree[index] = tree[index * 2] * tree[index * 2 + 1] % 1000000007


def multi(start, end, index, left, right):
    if start > right or end < left:
        return 1

    if left <= start and right >= end:
        return tree[index]
    
    mid = (start + end) // 2
    return multi(start, mid, index * 2, left, right) * multi(mid + 1, end, index * 2 + 1, left, right) % 1000000007


n, m, k = map(int, input().split())
arr = []
answer = []
tree = [0 for _ in range(n * 4)]

for _ in range(n):
    arr.append(int(input()))

init(0, n - 1, 1)
for i in range(m + k):
    a, b, c = map(int, input().split())
    
    if a == 1:
        update(0, n - 1, 1, b - 1, c)
        arr[b - 1] = c

    if a == 2:
        answer.append(multi(0, n - 1, 1, b - 1, c - 1))
for ans in answer:
    print(ans)