문제 링크
https://www.acmicpc.net/problem/11505
접근
연속된 구간에서 구간 곱을 구하는 문제이다. 그리고 숫자들이 바뀌고 그것대로 값을 갱신하는 문제이므로 세그먼트 트리로 풀어야겠다고 생각했다.
풀이
arr = [int(input()) for _ in range(n)]
b = math.ceil(math.log2(n)) + 1
node_n = 1 << b
seg = [0 for _ in range(node_n)]
def make_seg(idx, s, e):
if s == e:
seg[idx] = arr[s]
return seg[idx]
mid = (s + e) // 2
l = make_seg(idx * 2, s, mid)
r = make_seg(idx * 2 + 1, mid + 1, e)
seg[idx] = (l * r) % MOD
return seg[idx]
우선 세그먼트 트리를 만든다.
왼쪽 절반 구간의 구간곱과 오른쪽 절반 구간의 구간곱을 곱하여
현재 구간곱으로 취한다.
이를 반복하면 세그먼트 트리가 완성된다.
def change(idx, s, e):
if b - 1 < s or e < b - 1: # 범위 밖
return seg[idx]
if s == e:
seg[idx] = new
return new
# seg[idx] = seg[idx] // cur * new
# a/b mod M = (a mob M)/b mod M이 성립하지 않습니다
mid = (s + e) // 2
l = change(idx * 2, s, mid)
r = change(idx * 2 + 1, mid + 1, e)
seg[idx] = (l * r) % MOD
return seg[idx]값을 바꿔주는 역할을 하는 change() 함수이다.
이 부분에서 WA가 나왔는데, 나머지 연산을 하는 것에서 오답이 나왔다.
처음엔 구간합에서 한 것과 같이 바꿀 값 cur을 나눠주고 새 값 new를 곱해주는 식으로 하면 될 것이라 생각했다.
그러나 나머지 연산에서 a/b mod M 와 (a mob M)/b mod M 의 값이 다르게 나온다는 것을 깨달았다.
무슨 말인가 하면,
우리의 구간 곱이 1000000000000 (1조) 라고 하자.
이 구간 안에 어떤 수가 2였다고 치자.
이 수 2를 3으로 바꾸려고 한다.
그러면 (1조 // 2) * 3 을 해주면 될 것이다.
하지만 그러다보면 숫자가 너무 커져서 용량또한 커질 것이다.
그래서 우리는 이 1조를 MOD = 1,000,000,007 로 나누었던 것이다.
1조를 MOD 로 나누면 999993007 라는 나머지가 나오는데... 이 수는 2로 나누어지지도 않는다.
결론적으로 모듈로 연산이 된 수는 나누기 연산에서는 전혀 다른 값이 될 수 있다는 것이다.
우리가 예상한 값이 보장되지 않으므로 기존 값을 나누고 새 값을 곱하는 방법은 사용할 수 없다.
그리하여 어쩔 수 없이 해당 숫자가 포함된 범위의 모든 세그먼트 트리 노드들을 다시 만들어주는 방법을 사용하였다.
def change(idx, s, e):
if b - 1 < s or e < b - 1: # 범위 밖
return seg[idx]
if s == e:
seg[idx] = new
return new
mid = (s + e) // 2
l = change(idx * 2, s, mid)
r = change(idx * 2 + 1, mid + 1, e)
seg[idx] = (l * r) % MOD
return seg[idx]곱하기는 모듈로 연산에서 항상 그 값이 보장이 된다.
def get(idx, s, e):
# 탐색 영역 : s~e
if to < s or e < frm: # 범위 밖
return 1
mid = (s + e) // 2
if frm <= s and e <= to: # 탐색 영역이 b~c 완전히 안에 있음
return seg[idx]
else: # 탐색 영역이 더 큰 경우나 범위 걸친 경우
l = get(idx * 2, s, mid)
r = get(idx * 2 + 1, mid + 1, e)
return (l * r) % MOD마지막으로 구간 곱을 반환해주는 get() 함수이다.
탐색 영역이 s~e 이고, 우리가 구하고자 하는 구간 곱의 영역이 frm~to 라고 쳤을 때,
총 세가지 경우로 나눌 수 있다.
먼저 s~e 와 frm~to 가 전혀 다른 곳에 있는 경우이다.
이 경우 s~e 전 범위를 다 뒤져도 우리가 원하는 구간이 나오지 않는다. 아니 그냥 구간 자체가 다르므로 생각할 필요가 없는 것이다. 1을 반환해주자.
다음으로 탐색 영역 s~e 가 frm~to 사이에 완전히 들어가 있는 경우이다.
frm <= s~e <= to 이런 식으로 말이다.
이 경우 굳이 더 내려가 탐색하지 않고 그 자체가 다 쓰이므로 해당 구간 곱을 바로 리턴해준다.
(s~e 구간이 다 쓰여짐!)
마지막으로 탐색 영역 s~e 가 frm~to 사이에 완전히 들어가 있지 않은 경우이다.
범위가 걸쳐있는 경우 + s <= frm~to <= e 와 같은 경우이다.
이 경우 좌 우로 나누어 해당 구간 곱들을 구하고 그것을 곱한것을 반환한다.
(더 탐색할 필요가 있음!)
정답 코드
import math
import sys
sys.setrecursionlimit(10 ** 8) # pypy 제출시 삭제!
input = lambda: sys.stdin.readline().rstrip()
# in_range = lambda y,x: 0<=y<n and 0<=x<m
MOD = 1000000007
n, m, k = map(int, input().split())
arr = [int(input()) for _ in range(n)]
b = math.ceil(math.log2(n)) + 1
node_n = 1 << b
seg = [0 for _ in range(node_n)]
def make_seg(idx, s, e):
if s == e:
seg[idx] = arr[s]
return seg[idx]
mid = (s + e) // 2
l = make_seg(idx * 2, s, mid)
r = make_seg(idx * 2 + 1, mid + 1, e)
seg[idx] = (l * r) % MOD
return seg[idx]
def change(idx, s, e):
if b - 1 < s or e < b - 1: # 범위 밖
return seg[idx]
if s == e:
seg[idx] = new
return new
mid = (s + e) // 2
l = change(idx * 2, s, mid)
r = change(idx * 2 + 1, mid + 1, e)
seg[idx] = (l * r) % MOD
return seg[idx]
def get(idx, s, e):
# 탐색 영역 : s~e
if to < s or e < frm: # 범위 밖
return 1
mid = (s + e) // 2
if frm <= s and e <= to: # 탐색 영역이 b~c 완전히 안에 있음
return seg[idx]
else: # 탐색 영역이 더 큰 경우나 범위 걸친 경우
l = get(idx * 2, s, mid)
r = get(idx * 2 + 1, mid + 1, e)
return (l * r) % MOD
make_seg(1, 0, len(arr) - 1)
for _ in range(m + k):
a, b, c = map(int, input().split())
if a == 1:
cur = arr[b - 1]
new = c
change(1, 0, len(arr) - 1)
else:
frm, to = b - 1, c - 1
print(get(1, 0, len(arr) - 1) % MOD)
