073 구간 곱 구하기

첫번째 코드

 

구간 합 구하기를 세그먼트로 풀어보았다면 아래 코드 이해는 어렵지 않을 것이다.

하지만 곱하기를 이용하므로 MOD를 이용한다는 부분 정도를 생각한다면

금방 변형해서 풀 수 있는 문제이다.

 

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
treeHeight = 0
length = n
MOD = 1000000007

while length != 0:
    length //= 2
    treeHeight += 1

treeSize = 2 ** (treeHeight + 1)
leftNodeStartIndex = treeSize//2 - 1
tree = [1] * (treeSize + 1)

for i in range(leftNodeStartIndex + 1, leftNodeStartIndex + n + 1):
    tree[i] = int(input())

def setTree(i):
    while i != 1:
        tree[i // 2] = tree[i//2] * tree[i] % MOD
        i -= 1

setTree(treeSize - 1)

def changeVal(index, value):
    tree[index] = value
    while index > 1:
        index = index // 2
        tree[index] = tree[index * 2] % MOD * tree[index * 2 + 1] % MOD

def getMul(s, e):
    partMul = 1
    while s <= e:
        if s % 2 == 1:
            partMul = partMul * tree[s] % MOD
            s += 1
        if e % 2 == 0:
            partMul = partMul * tree[e] % MOD
            e -= 1
        s = s // 2
        e = e // 2
    return partMul

for _ in range(m + k):
    question, s, e = map(int, input().split())
    if question == 1:
        changeVal(leftNodeStartIndex + s, e)
    elif question == 2:
        s = s + leftNodeStartIndex
        e = e + leftNodeStartIndex
        print(getMul(s, e))

 

통과

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/11505.%E2%80%85%EA%B5%AC%EA%B0%84%E2%80%85%EA%B3%B1%E2%80%85%EA%B5%AC%ED%95%98%EA%B8%B0

programmers/백준/Gold/11505. 구간 곱 구하기 at main · ornni/programmers