백준/ Gold 1 문제 , 백준 파이썬 11505 , 구간 곱 구하기 [세그먼트 트리]

백준/ Gold 1 문제 , 백준 파이썬 11505 , 구간 곱 구하기 [세그먼트 트리]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
곱하기라 구간 곱을 구해줄때 return 1 을 해줘야했는데 return 0 으로 잘못생각해서 시간이 좀 걸렸다.

 

 

 

문제 출처

https://www.acmicpc.net/problem/11505

11505번: 구간 곱 구하기

 

참고

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Gold-1-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-2042-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC

백준/ Gold 1 문제 , 백준 파이썬 2042 , 구간 합 구하기 [세그먼트 트리]

 

 

이 문제를 풀기 전에 구간합 구하기 문제를 안 풀어봤다면 먼저 풀어보자. 그럼 이해가 더 빠를 것이다.

 

 

풀이

 

 

1. 세그먼트 트리 생성 함수

 

이전과 다르게 구간곱을 구해줘야 하므로 tree에도 곱하기연산을 적용하여 할당한다.

 

 

2. 특정 노드의 값을 변경시키는 함수

 

tree에는 해당 노드의 자식노드들끼리 곱한 값을 저장한다.

 

 

 

3. 구간 곱을 구해주는 함수

 

구간 합을 구해줄때는 return 0 을 해줬지만 곱하기에 0을 return 시켜버리면 무조건 0이 되어버리기때문에 1을 리턴시켜줘야한다.

 

이후 재귀 호출할때도 곱하기 연산으로 바꿔준다.

 

 

 

4. 입력 받기 및 각 함수들 호출

 

a가 1일때 update함수를 호출해주고 배열의 값도 수정해주자.

 

 

 

 

 

정답

 

 

import sys
input=sys.stdin.readline

tmp=1000000007

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

def update(start,end,index,what,value):
    if what < start or what > end:
        return
    if start==end:
        tree[index]=value
        return
    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]%tmp
    
def interval_multi(start,end,index,left,right):
    if end<left or start>right:
        return 1
    if left<=start and right>=end:
        return tree[index]
    mid=(start+end)//2
    return interval_multi(start,mid,index*2,left,right)*interval_multi(mid+1,end,index*2+1,left,right)%tmp
    

N,M,K=map(int,input().split())
arr=[int(input().rstrip()) for _ in range(N)]
tree=[0]*(N*4)

init(0,N-1,1)

for j 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
    elif a==2:
        print(interval_multi(0,N-1,1,b-1,c-1))