본문 바로가기

카테고리 없음

[백준 5676번] 음주 코딩 (Python3)

import sys
input = sys.stdin.readline

def makeseg(start,end,x):
  if start == end:
    segtree[x] = data[start]
  else:
    mid = (start+end)//2
    segtree[x] = makeseg(start,mid,x*2) * makeseg(mid+1,end,x*2+1)
  return segtree[x]

def updateseg(i,v,start,end,x):
  if start == end:
    segtree[x] = v
  else:
    mid = (start+end)//2
    if i <= mid:
      segtree[x] = updateseg(i,v,start,mid,x*2) * segtree[x*2+1]
    else:
      segtree[x] = segtree[x*2] * updateseg(i,v,mid+1,end,x*2+1)
  return segtree[x]

def printseg(a,b,start,end,x):
  if a == start and b == end:
    return segtree[x]
  mid = (start+end)//2
  if b <= mid:
    return printseg(a,b,start,mid,x*2)
  if a > mid:
    return printseg(a,b,mid+1,end,x*2+1)
  return printseg(a,mid,start,mid,x*2)*printseg(mid+1,b,mid+1,end,x*2+1)

while True:
  try :
    N,K = map(int,input().split())
  except :
    break
  data = [*map(lambda x:-1 if x<0 else 1 if x>0 else 0,map(int,input().split()))]
  segtree = {}

  makeseg(0,N-1,1)
  result = ""
  for i in range(K):
    q,i,j = input().split()
    if q == "C":
      updateseg(int(i)-1,(lambda x:-1 if x<0 else 1 if x>0 else 0)(int(j)),0,N-1,1)
    else:
      result += (lambda x:"-" if x<0 else "+" if x>0 else "0")(printseg(int(i)-1,int(j)-1,0,N-1,1))  
  print(result)

 

전형적인 세그먼트 트리 문제 +1

 

입력방식이 약간 까다롭다. 테스트케이스 개수가 주어지지 않았기 때문에 try except를 활용해야하고, 함수에 문자와 숫자가 같이 포함되어있어 map int를 이용할 수 없다. 그 외 다른건 어려운건 없다.

 

곱의 세그먼트 트리를 사용하되, 모든 숫자를 크기에 따라 -1,0,1로 바꿔주면 된다.

 

 lambda 함수를 이용하면 쉽게 -1,0,1로 바꿀 수 있다.

 

 

오늘의 교훈) 세그먼트 트리는 사기다