내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
자동차 공장
ps:problems:boj:2820
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 자동차 공장 ====== ===== 풀이 ===== * [[ps:구간 쿼리#오일러 경로 테크닉]]이 추가된 구간 쿼리 문제. * [[ps:구간 쿼리#오일러 경로 테크닉]]을 적용해서 트리를 리스트로 변환해주기만 하면, 단순히 구간 업데이트 + 포인트 쿼리 문제가 된다. 이는 [[ps:구간 쿼리#구간 합|인접합 값의 차이로 구성된 배열]]을 만들어서 포인트 업데이트 + 구간 쿼리로 변환한 뒤, [[ps:펜윅 트리]]를 이용해서 해결이 가능하다. * 전처리에는 오일러 경로 테크닉을 적용하는 데에 O(n), 펜윅 트리를 만드는데에 O(n), 모두 O(n)이 걸린다. 각각의 쿼리를 처리 하는 것은 O(logn)이 걸리므로 m개의 쿼리는 모두 O(mlogn)에 처리 가능하다. 따라서 총 시간 복잡도는 O(n+mlogn) * 실수하기 쉬운 포인트는, p a x 쿼리에서, a의 월급은 변하지 않는다. 즉, a를 루트로 하는 서브트리 전체를 업데이트 하는 것이 아니라, 서브트리에서 a를 제외한 나머지만 업데이트 해줘야 한다. a를 루트로 하는 서브트리를 오일러 경로 테크닉으로 구간으로 변환했을때, a는 구간의 맨 앞에 오게 되므로, a를 제외한 구간을 구하려면 구간의 시작 위치에 +1을 해주기만 하면 된다. * 한가지 더 주의할 점은, p a x 쿼리는 a가 아무 부하가 없을 경우에도 들어올 수 있다. 이 경우에 인덱스에러가 나지 않도록 처리해줄 필요가 있다. ===== 코드 ===== <dkpr py> """Solution code for "BOJ 2820. 자동차 공장". - Problem link: https://www.acmicpc.net/problem/2820 - Solution link: http://www.teferi.net/ps/problems/boj/2820 """ import sys from teflib import fenwicktree from teflib import tgraph def euler_tour_techinique(tree, root): subtree_ranges = [[None, None] for _ in tree] order = 0 for node in tgraph.dfs(tree, root, yields_on_leave=True): if subtree_ranges[node][0] is None: subtree_ranges[node][0] = order order += 1 else: subtree_ranges[node][1] = order return subtree_ranges def main(): N, M = [int(x) for x in sys.stdin.readline().split()] tree = [[] for _ in range(N)] salaries = [int(sys.stdin.readline())] for i in range(1, N): salary, boss = [int(x) for x in sys.stdin.readline().split()] salaries.append(salary) tree[boss - 1].append(i) subtree_ranges = euler_tour_techinique(tree, 0) fenwick = fenwicktree.FenwickTree(N + 1) for i in range(M): query = sys.stdin.readline().split() if query[0] == 'p': a, x = int(query[1]), int(query[2]) beg, end = subtree_ranges[a - 1] beg += 1 if beg < end: fenwick.update(beg, x) fenwick.update(end, -x) else: a = int(query[1]) pos = subtree_ranges[a - 1][0] print(fenwick.query(0, pos + 1) + salaries[a - 1]) if __name__ == '__main__': main() </dkpr> * Dependency: [[:ps:teflib:fenwicktree#FenwickTree|teflib.fenwicktree.FenwickTree]], [[:ps:teflib:tgraph#dfs|teflib.tgraph.dfs]] {{tag>BOJ ps:problems:boj:플래티넘_3}}
ps/problems/boj/2820.txt
· 마지막으로 수정됨: 2021/05/04 10:40 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로