[백준/2820] 자동차 공장 (Python)

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

2820번: 자동차 공장

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 01:08:55

 

---

 

문제 설명

 

 

상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. (상근이는 모든 사람의 상사이다) 상근이의 번호는 1번이고, 나머지 직원의 번호는 2부터 N이다.

모든 직원은 자신의 모든 부하 직원(직속 부하와 부하의 부하등등을 모두 포함)의 월급을 인상하거나 삭감할 수 있다. 상근이는 권력 남용을 막기 위해 직원의 월급을 모니터링 하려고 한다.

월급의 변화를 모니터링하는 프로그램을 작성하시오.

모든 직원의 월급은 항상 양의 정수이고 2^31-1 이하이다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 직원의 수 N과 월급 변화와 조사 쿼리의 수 M이 주어진다. (1 ≤ N, M ≤ 500,000)

다음 N개 줄의 i번째 줄에는 직원 i의 초기 월급과 상사의 번호가 주어진다. (상근이는 상사가 없기 때문에, 초기 월급만 주어진다)

다음 M개 줄에는 월급 변화와 조사 쿼리가 주어진다.

1. p a x가 주어진 경우 a의 모든 부하의 월급을 x만큼 증가시킨다. (-10,000 ≤ x ≤ 10,000)
2. u a가 주어진 경우에는 a의 월급을 출력한다.

 

출력

 

입력으로 u가 주어질 때마다 해당하는 직원의 월급을 출력한다.

 

입력 예시

 

2 3
5
3 1
p 1 5
u 2
u 1

 

출력 예시

 

8
5

 

 

---

 

풀이

 

 

이 문제를 참고하자.

 

2023.12.28 - [PS/백준] - [백준/16404] 주식회사 승범이네 (Python)

[백준/16404] 주식회사 승범이네 (Python)

 

핵심은 동일하다. 그대로 트리 형태로 진행하게 되면, 극단적으로 편향된 경우 O(NM)의 시간복잡도가 소요된다. 따라서 오일러 경로 테크닉을 이용해 세그먼트 트리 형태로 전환하고, 구간 업데이트 및 서칭을 로그 시간복잡도에 끝낼 수 있는 lazy propagation 을 사용해서 해결한다.

 

단, 파이썬은 매우 느린 언어다. 즉 오일러 경로 테크닉, 트리의 업데이트, 서칭 모두 비재귀 방식으로 구현되어야 함에 주의하자.   

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
children = [list() for _ in range(N+1)]
parents = [[0, 0] for _ in range(N+1)]
index = [[0, 0] for _ in range(N+1)]
salary = [0]*(N+1)

def dfs():
  q = [(1, 0)]
  leaf_q = []
  cnt = 0
  while q:
    n, p = q.pop()
    cnt += 1
    index[n][0] = cnt
    if not children[n]:
      leaf_q.append(n)
      index[n][1] = cnt
      continue
    for c in children[n]:
      q.append((c, n))
  while leaf_q:
    n = leaf_q.pop()
    p = parents[n][0]
    if p :
      if index[p][1] < index[n][1] :
        index[p][1] = index[n][1]
      parents[p][1] -= 1
      if not parents[p][1] :
        leaf_q.append(p)

def propagate(start, end, idx):
  if start != end:
    lazy[idx*2 + 1] += lazy[idx]
    lazy[idx*2] += lazy[idx]
  else:
    tree[idx] += lazy[idx]
  lazy[idx] = 0

def update(left, right, val):
  q = [(0, N, 1)]
  while q :
    s, e, i = q.pop()
    propagate(s, e, i)
    if left > e or right < s :
      continue
    if left <= s <= e <= right :
      lazy[i] += val
      propagate(s, e, i)
      continue
    mid = (s + e) // 2
    q.append((s, mid, i*2))
    q.append((mid+1, e, i*2+1))

def search(target):
  start, end, idx = 0, N, 1
  while start < end:
    propagate(start, end, idx)
    mid = (start + end) // 2
    if target <= mid:
      end = mid
      idx = idx*2
    else :
      start = mid+1
      idx = idx*2+1
  propagate(start, end, idx)
  return tree[idx]

salary[1] = int(input())
for i in range(2, N + 1):
  s, p = map(int, input().split())
  salary[i] = s
  parents[i][0] = p
  parents[p][1] += 1
  children[p].append(i)

dfs()
tree = [0]*(4*N + 4)
lazy = [0]*(4*N + 4)

for _ in range(M):
  q, *cmd = input().split()
  if q == 'p':
    a, b = map(int, cmd)
    left, right = index[a]
    if left == right :
      continue
    update(left + 1, right, b)
  else:
    a = int(cmd[0])
    result = search(index[a][0])
    print(result + salary[a])

풀이 완료!