내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
국제 메시 기구
ps:problems:boj:17429
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 국제 메시 기구 ====== ===== 풀이 ===== * HLD + lazy segment tree * 쿼리 종류가 다양해서 복잡해 보이지만, 결국은 기본적인 연산들이고, 풀이 자체는 새로운 아이디어를 필요로 하는 것은 없다. * 트리에서의 경로 쿼리와, 서브트리 쿼리를 구간 쿼리로 변환하는 것은 Heavy Light Decomposition의 기본적인 연산들이다 * 구간에 대해서 구간 합 업데이트/구간 곱 업데이트/구간 합 쿼리를 처리하는 것은, 두 종류의 업데이트를 x := ax+b 의 선형 변환 업데이트로 합쳐서 처리할 수 있다. 이것을 레이지 세그먼트 트리로 처리하는 것은 정확히 [[ps:problems:boj:13925]] 와 동일하다. 풀이는 이쪽을 참조. * HLD와 세그먼트 트리 구축은 O(n)에 가능하고, 경로에 대한 업데이트와 쿼리는 O(log^2n)에, 서브트리에 대한 쿼리와 업데이트는 O(logn)에 처리 가능하다. 총 시간 복잡도는 O(n+qlog^2n) * n<=500,000, q<=100,000 인데 시간 맞추기가 꽤 타이트하다. Python으로는 TLE가 나고, PyPy로 제출해야 약 8000ms 로 겨우 통과된다, ===== 코드 ===== (다이아몬드 이상은 코드 생략) * Dependency * [[ps:teflib:segmenttree#LazySegmentTree|teflib.segmenttree.LazySegmentTree]] * [[ps:teflib:ttree#HeavyLightDecomposition|teflib.ttree.HeavyLightDecomposition]] {{tag>BOJ ps:problems:boj:다이아몬드_4}}
ps/problems/boj/17429.txt
· 마지막으로 수정됨: 2021/05/28 15:29 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로