[백준 11505번] 파이썬 - 구간 곱 구하기

백준 11505_구간 곱 구하기

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

# 조건

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

# 접근 방법

• 세그먼트 트리로 구간 곱을 구해주면 된다.
  • 참고 - https://cheon2308.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%ACSegment-Tree
• 세그먼트 트리 초기화는 start, end, now 인자를 받아서 start == end인 경우 세그먼트 트리에 기록해주면 된다.

def init(now, start, end):  
    if start == end:  
        tree[now] = nums[start]  
        return tree[now]  
    mid = (start+end)//2  
    tree[now] = init(now*2, start, mid) * init(now*2+1, mid+1, end)  
    return tree[now]  


N, M, K = map(int, input().split())  
H = ceil(log(N, 2))  
seg_size = 1<<(H+1)  
nums = [0]  
for _ in range(N):  
    nums.append(int(input()))  

tree = [0] * seg_size  

init(1, 1, N)

• 초기화 이후, 업데이트를 진행하여야 되는데 주어지는 쿼리에 따라 변경해줄 것이다.
• start, end 는 현재 노드의 포용 범위, now는 현재 노드, idx는 target 노드, val은 변경 값이다.
  • 리프 노드라면 target 값만큼 변경해주고, 이후 부모 노드의 값을 update해주면 된다.

def update(start, end, now, idx, val):  
    if start > idx or idx > end:  
        return tree[now]  
    if start == end:  
        tree[now] = val  
    else:  
        mid = (start + end) // 2  
        update(start, mid, now * 2, idx, val)  
        update(mid + 1, end, now * 2 + 1, idx, val)  
        tree[now] = tree[2 * now] * tree[2 * now + 1] % 1000000007  

• 쿼리 출력 또한 비슷하다.
• 범위에 따라서, 구해주면 된다.
  • 요청 구간이 현재 포용 구간을 벗어난다면 곱셈이므로 1 리턴
  • 완전히 포함한다면 좌표의 값 리턴
  • 현재 포용 구간이 현재 요청 구간을 완전히 포함한 경우, 절반씩 나눠 재귀적으로 탐색하면된다.

전체 코드

import sys  

sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from math import *  


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


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


def update(start, end, now, idx, val):  
    if start > idx or idx > end:  
        return tree[now]  
    if start == end:  
        tree[now] = val  
    else:  
        mid = (start + end) // 2  
        update(start, mid, now * 2, idx, val)  
        update(mid + 1, end, now * 2 + 1, idx, val)  
        tree[now] = tree[2 * now] * tree[2 * now + 1] % 1000000007  


N, M, K = map(int, input().split())  
H = ceil(log(N, 2))  
seg_size = 1 << (H + 1)  
nums = []  
for _ in range(N):  
    nums.append(int(input()))  

tree = [0] * seg_size  

init(1, 0, N - 1)  

for _ in range(M + K):  
    a, b, c = map(int, input().split())  
    if a == 1:  
        update(0, N - 1, 1, b - 1, c)  
    else:  
        print(query(1, 0, N - 1, b - 1, c - 1))