너무도 흔한 세그먼트 트리 문제이다.
하지만, 주의해야 할 부분이 몇 가지 있다.
주의해야 할 점
1. 구간곱 문제이므로 수가 커진다. 하지만, 이 문제에서는 음,양,0만 판별하면 되므로 모든 수를 -1, 0, 1로 바꿔준다.
2. 문제에 TC(테스트 케이스)가 주어지지 않았다. C++에선 while scanf 사용이 가능하지만 Python3에서는 다른 방법을 사용한다.
TC가 주어지지 않는 경우
Python3에서는 Try - Except 구문으로 대체할 수 있다.
while True:
try:
a, b = map(int, input().split())
except Exception:
break
#Your Code 입력의 끝인 EOF가 입력되면 Exception으로 빠지면서 while문이 break되는 원리이다.
처음에 이 방법을 몰라서 C++로 옮겨 적으려고 하다가 해법을 찾아서 공유하기 위해 글을 썼다.
런타임 에러 & 틀렸습니다 & 시간 초과
"맞왜틀.."을 호소하며 어디가 문제인지 몰랐다. 위에서 말한 TC가 주어지지 않는 경우에서 어떻게 대처를 할지 몰라 헤맸던 것이 가장 컸다. 처음엔 while 없이 시도했다가 당연히 틀리게 됐고 이후엔 while 문을 끝내지 않고 시도했다가 런타임 에러가 떴다...
보통의 문제들은 TC가 주어지는데 이 문제와 일부 문제들은 TC가 주어지지 않아서 위와 같은 방법을 사용해야 한다.
문제에 좀 더 친절히 설명이 되어있으면 좋았을 부분이다.
시간초과 Python3 소스코드
위의 링크에서 살펴보면, 46~47 줄에서 조건문에 query함수를 실행시킨다. 무려 두 번이다..
처음엔 몰랐다.. 맞왜틀...은.. 이유가 있었다.
항상 잘 살펴보자.
통과한 소스코드
import sys
input = sys.stdin.readline
tree = list()
nodes = list()
def pmz(num):# 양수,음수,0 반환하는 함수
if num>0:return 1
elif num<0:return -1
else: return 0
def update(start,end,index,changeIdx,changeNum):
if changeIdx <start or changeIdx>end:return
if start == end:
tree[index] = changeNum
return
mid = (start+end)//2
update(start,mid,index*2,changeIdx,changeNum)
update(mid+1,end,index*2+1,changeIdx,changeNum)
tree[index] = tree[index*2]*tree[index*2+1]
def query(start,end,index,left,right):
if left>end or right<start:return 1
if left<=start and right>=end:
return tree[index]
mid = (start+end)//2
return query(start,mid,index*2,left,right)*query(mid+1,end,index*2+1,left,right)
def init(start,end,index):
if start==end:
nodes[start] = pmz(nodes[start])
tree[index] = nodes[start]
return tree[index]
mid = (start+end)//2
tree[index] = init(start,mid,index*2)*init(mid+1,end,index*2+1)
return tree[index]
if __name__ == "__main__":
while True:
try:
n,k = map(int,input().rstrip().split())
tree = [0]*(n*4)
nodes = list(map(int,input().rstrip().split()))
answer = ''
init(0,n-1,1)
for _ in range(k):
lst = input().rstrip().split()
if lst[0] == 'C':#수정
i,V = map(int,(lst[1],lst[2]))
nodes[i-1]=pmz(V)
update(0,n-1,1,i-1,pmz(V))
else:#출력
i,j = map(int,(lst[1],lst[2]))
res = query(0,n-1,1,i-1,j-1)
if(res==0):answer+='0'
elif(res>0):answer+='+'
else:answer+='-'
print(answer)
except Exception:
break
