[Python3] 11505 구간 곱 구하기 - 골드 1

• 2022.02.11 포스팅 기준 solved.ac 문제 등급 : 골드 1
• 단계별로 풀어보기 -> 세그먼트 트리
• 알고리즘 분류
  • 자료구조
  • 세그먼트 트리

 

<링크>
https://www.acmicpc.net/problem/11505

11505번: 구간 곱 구하기

시간제한	메모리제한
1 초	256 MB

 

---

<문제>
어떤 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

 

---

<풀이 접근>

구간의 합을 구하는 문제와 달리, 이 문제는 구간의 곱을 반환하는 함수가 필요합니다.
구간의 밖에서 덧셈의 항등원인 0을 반환했던 구간합 문제와 달리, 이번에는 목표 구간의 밖에서 곱셈의 항등원인 1을 반환하도록 하는 점에 유의합니다.
다른 부분에 대한 설명은 이전 포스팅 https://qodelog.tistory.com/3 을 참고해주세요. 

import sys
import math
input = sys.stdin.readline

P = 1000000007 # 나머지 계산을 위한 소수

n, m, k = map(int, input().split())

# nums의 인덱스를 1부터 사용하기 위해 앞에 [0]을 붙여줍니다.
nums = [0] + [int(input()) for _ in range(n)]

# m+k개의 쿼리를 arr리스트에 받습니다.
arr = [[*map(int, input().split())] for _ in range(m + k)]

# 세그먼트 트리의 크기를 아래와 같이 정하는 이유는 https://qodelog.tistory.com/2를 참고하세요.
seg_tree = [0 for _ in range((1 << int(math.ceil(math.log2(n + 1)))+1) + 1)]


# 주어진 nums의 값들을 이용해 세그먼트 트리를 초기화 합니다.
def make_tree(tree, start, end, v):
    if start == end:
        tree[v] = nums[start] % P
    else:
        mid = (start + end) // 2
        tree[v] = (make_tree(tree, start, mid, v * 2) * make_tree(tree, mid + 1, end, v * 2 + 1)) % P
    return tree[v]


# a=2인 쿼리의 경우, 하위 구간의 곱을 반환합니다.
def mul_tree(tree, start, end, v, left, right):
    if end < left or right < start:
        return 1
    elif left <= start and end <= right:
        return tree[v]
    else:
        mid = (start + end) // 2
        return (mul_tree(tree, start, mid, v * 2, left, right)
                * mul_tree(tree, mid + 1, end, v * 2 + 1, left, right)
                ) % P


# a=1인 쿼리의 경우 old값을 new값으로 바꾸고 트리를 갱신합니다.
def update_tree(tree, start, end, v, idx, old, new):
    if start <= idx <= end:
        if start != end:
            mid = (start + end) // 2
            tree[v] = (update_tree(tree, start, mid, v * 2, idx, old, new)
                       * update_tree(tree, mid + 1, end, v * 2 + 1, idx, old, new)
                       ) % P
        elif start == idx:
            tree[v] = new
    return tree[v]


make_tree(seg_tree, 1, n, 1)
res = ''

for a, b, c in arr:
    if a == 1:
        update_tree(seg_tree, 1, n, 1, b, nums[b], c)
        nums[b] = c
    elif a == 2:
        res += str(mul_tree(seg_tree, 1, n, 1, b, c)) + '\n'

print(res.rstrip())

 

코드의 수행 결과는 아래와 같습니다.

이 문제 역시 정답 코드들 중 상위권의 빠른 코드가 500ms 안쪽으로 나옵니다.
최적화의 여지가 있어 보입니다...

---

<마무리>
구간의 합을 구하는 문제와 비슷한 방법으로 풀이를 작성했습니다. 
다음에는 트리의 최댓값, 최솟값을 구하는 문제를 다루면서 어떤 부분이 다른지 살펴보면 좋을 것 같습니다.