아이디어
간격 제품을 세그먼트 트리로 저장하고 변경 또는 계산이 필요한 간격을 신속하게 처리합니다.
설명
구간의 합 2042를 구하는 문제와 마찬가지로 합이 아니라 곱만 저장하면 됩니다.
구간 곱을 계산하기 위해 N보다 큰 2의 최소 제곱 크기의 2배로 채워진 목록의 트리를 만듭니다.
트리의 리프 노드에는 순서대로 N개의 번호가 부여되고 두 자식 노드의 곱은 for 문에서 각 부모 노드에 저장됩니다.
이후 for 문에서 a가 1이면 트리의 리프 노드 개수를 변경한 후 업데이트 함수를 호출하고, a가 2이면 곱하기 함수를 호출한다.
함수 업데이트에서 부모 노드는 리프 노드부터 순서대로 재계산되고 루트 노드가 재귀 호출에 의해 종료되면 종료됩니다.
곱하기 함수는 결과 값 res에 리프 노드부터 해당 노드의 부모 노드까지 순서대로 간격 곱을 곱한다.
부모 노드의 값은 두 자식 노드의 값의 곱입니다. 즉, 다음과 같이 형제 노드 중 하나만 포함하는 경우 예: s%2 == 1 또는 e%2 == 0
이 노드의 값에 res를 곱한 후 부모 노드의 값이 곱해지지 않도록 인덱스를 이동합니다.
구간합에서 트리의 초기값이 덧셈의 항등식인 0으로 채워지면 구간곱은 곱셈의 항등식인 1로 채워집니다.
또한 중간 계산 과정에서 1,000,000,007로 나눈 나머지가 저장됩니다.
import sys
input = sys.stdin.readline
def update(idx):
while idx > 0:
tree(idx) = tree(idx*2)*tree(idx*2+1)%1000000007
idx //= 2
def multiply(s, e):
res = 1
while s <= e:
if s%2:
res *= tree(s)
s += 1
if e%2 == 0:
res *= tree(e)
e -= 1
s, e = s//2, e//2
res %= 1000000007
return res
N, M, K = map(int, input().split())
n = 1
while n < N:
n *= 2
tree = (1)*(n*2)
tree(n:n+N) = (int(input()) for _ in range(N))
for i in range(n-1, 0, -1):
tree(i) = tree(i*2)*tree(i*2+1)%1000000007
for _ in range(M+K):
a, b, c = map(int, input().split())
if a == 1:
tree(n+b-1) = c
update((n+b-1)//2)
else:
print(multiply(n+b-1, n+c-1))
