[백준/5676] 음주 코딩 (Python)

Problem : https://www.acmicpc.net/problem/5676

25241번: 가희와 사직 구장

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:13:38

 

---

 

문제 설명

 

 

오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다.

상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다.

먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X1, X2, ... XN을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다.

 

• 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다.
• 곱셈: 선영이는 상근이에게 i와 j를 말한다. 상근이는 Xi × Xi+1 × ... × Xj-1 × Xj 의 값이 양수인지, 음수인지, 0인지를 대답한다.

곱셈 명령에서 상근이가 대답을 잘못했을 때의 벌칙은 소주 한 잔이다. 상근이는 갑자기 대회가 걱정되기 시작했다. 또, 상근이는 발머의 피크 이론을 증명하고 싶지 않다.

다행히 선영이는 상근이에게 노트북 사용을 허락했다. 상근이는 자신의 수학 실력보다 코딩 실력을 더 믿는다.

상근이를 돕는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 수열의 크기 N과 게임의 라운드 수 K가 주어진다. (1 ≤ N, K ≤ 105)

둘째 줄에는 총 N개의 숫자 Xi가 주어진다. (-100 ≤ Xi ≤ 100)

다음 K개 줄에는 선영이가 내린 명령이 주어진다. 명령은 C 또는 P로 시작한다.

C로 시작하는 명령은 변경 명령이고, 그 다음에 i와 V가 주어진다. Xi를 V로 변경하는 명령이다. (1 ≤ i ≤ N, -100 ≤ V ≤ 100)

P로 시작하는 명령은 곱셈 명령이고, 그 다음에 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

각 테스트 케이스에 곱셈 명령은 항상 한 번 이상있다.

 

출력

 

각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.

 

입력 예시

 

4 6
-2 6 0 -1
C 1 10
P 1 4
C 3 7
P 2 2
C 4 -5
P 1 4
5 9
1 5 -2 4 3
P 1 2
P 1 5
C 4 -5
P 1 5
P 4 5
C 3 0
P 1 5
C 4 -5
C 4 -5

 

출력 예시

 

0+-
+-+-0

 

 

---

 

풀이

 

세그먼트 트리를 이용하는 기본 문제. 값이 너무 커질 수 있고, 우리는 음수, 양수, 0 여부만을 판별하면 되므로 부호값만을 저장하여 연산해주도록 하자. 시간복잡도는 O(KlogN)이 소요된다.

 

풀이 코드

import sys
input = sys.stdin.readline

def sign(n) :
  if n > 0 :
    return 1
  if n == 0 :
    return 0
  return -1

def init(N, nums, tree) :
  for i in range(N) :
    tree[i+N] = sign(nums[i])
  for i in range(N-1, -1, -1) :
    tree[i] = tree[i<<1] * tree[i<<1|1]

def update(N, tree, idx, val) :
  idx += N
  tree[idx] = sign(val)
  while idx :
    idx >>= 1
    tree[idx] = tree[idx<<1] * tree[idx<<1|1]

def query(N, tree, l, r) :
  l += N
  r += N
  res = 1
  while l <= r :
    if l % 2 == 1 :
      res *= tree[l]
      l += 1
    if r % 2 == 0 :
      res *= tree[r]
      r -= 1
    l >>= 1
    r >>= 1
  return res

def solve() :
  N, K = map(int, input().split())
  tree = [0]*(2*N)
  nums = list(map(int, input().split()))
  ans = ''
  init(N, nums, tree)
  for _ in range(K) :
    q, *cmd = input().split()
    if q == 'C' :
      i, v = map(int, cmd)
      update(N, tree, i-1, v)
    else :
      i, j = map(int, cmd)
      res = query(N, tree, i-1, j-1)
      if res == 1 :
        res = '+'
      else :
        res = '-' if res < 0 else '0'
      ans += res
  print(ans)

while True :
  try :
    solve()
  except :
    break

풀이 완료!