[백준/1275] 커피숍2 (Python)

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

1275번: 커피숍2

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:15:23

 

---

 

문제 설명

 

 

모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.)

어느 날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다.

그 게임은 다음과 같은 규칙을 갖는다.

N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그러면 동호는 “네 알겠습니다.”라고 한 뒤에 다시 상대방이 동호가 했던 것처럼 “8~9번째 수의 합은 무엇이죠?”라고 묻게된다. 이 것을 번갈아 가면서 반복하는 게임이다.

당신은 이 게임의 심판 역을 맡았다. 요컨대, 질문에 대한 답들을 미리 알아야 한다는 것이다.

당신의 머리가 출중하다면 10만개 가량 되는 정수와 10만턴 정도 되는 게임을 기억할 수 있을 것이다. 몇판 이 게임을 즐기던 동호는 많은 사람들이 이 게임을 하기를 바라게 되었고, 당신에게 심판 프로그램을 구현해달라고 요청했다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하여라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어진다.

입력되는 모든 수는 -231보다 크거나 같고, 231-1보다 작거나 같은 정수이다.

 

출력

 

한 턴마다 구한 합을 한 줄마다 한 개씩 출력한다.

 

입력 예시

 

5 2
1 2 3 4 5
2 3 3 1
3 5 4 1

 

출력 예시

 

5
10

 

 

---

 

풀이

 

N, Q가 매우 크고(약 10^6 이상) 쿼리 동안 N의 넘버 구간합을 구하거나, 업데이트해야 한다? 그럼 일단 세그먼트 트리를 써 보도록 하자. 공간복잡도와의 트레이드 오프를 통해서, 트리 형식으로 구성된 자료 구조이다. 중간값을 미리 구해놓는 방식은 매우 편리하며, 한 번의 쿼리를 처리할 때 평균적으로 O(logN)의 복잡도를 지니게 된다. 세그먼트 트리를 쓸 수 있느냐? 라고 물어보는 문제.

 

풀이 코드

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
num_list = list(map(int, input().split()))

class SegTree() :
  def __init__(self) :
    self.tree = [0]*(4*N)
    self._init(1, 0, N-1)

  def _init(self, idx, start, end) :
    if start == end :
      self.tree[idx] = num_list[start]
      return

    mid = (start + end) // 2
    self._init(idx*2, start, mid)
    self._init(idx*2+1, mid+1, end)
    self.tree[idx] = self.tree[idx*2] + self.tree[idx*2+1]

  def calculate(self, x, y) :
    if x > y :
      x, y = y, x
    return self._calculate(1, 0, N-1, x-1, y-1)

  def _calculate(self, idx, start, end, x, y) :
    if y < start or x > end :
      return 0
    if x <= start <= end <= y :
      return self.tree[idx]

    mid = (start + end) // 2
    left = self._calculate(idx*2, start, mid, x, y)
    right = self._calculate(idx*2+1, mid+1, end, x, y)
    return left + right
    
  def update(self, a, b) :
    self._update(1, 0, N-1, a-1, b)

  def _update(self, idx, start, end, target, val) :
    if target < start or target > end :
      return
    if start == end == target:
      self.tree[idx] = val
      return

    mid = (start + end) // 2
    self._update(idx*2, start, mid, target, val)
    self._update(idx*2+1, mid+1, end, target, val)
    self.tree[idx] = self.tree[idx*2] + self.tree[idx*2+1]

segtree = SegTree()
for _ in range(Q) :
  x, y, a, b = map(int, input().split())
  print(segtree.calculate(x, y))
  segtree.update(a, b)

풀이 완료!