사용자 도구

사이트 도구


ps:problems:boj:17429

국제 메시 기구

ps
링크https://www.acmicpc.net/problem/17429
출처BOJ
문제 번호17429
문제명국제 메시 기구
레벨다이아몬드 4
분류

구간 쿼리

시간복잡도O(n+qlog^2(n)
인풋사이즈n<=500,000, q<=100,000
사용한 언어PyPy
제출기록332516KB / 8212ms
최고기록8212ms
해결날짜2021/05/24

풀이

  • HLD + lazy segment tree
  • 쿼리 종류가 다양해서 복잡해 보이지만, 결국은 기본적인 연산들이고, 풀이 자체는 새로운 아이디어를 필요로 하는 것은 없다.
  • 트리에서의 경로 쿼리와, 서브트리 쿼리를 구간 쿼리로 변환하는 것은 Heavy Light Decomposition의 기본적인 연산들이다
  • 구간에 대해서 구간 합 업데이트/구간 곱 업데이트/구간 합 쿼리를 처리하는 것은, 두 종류의 업데이트를 x := ax+b 의 선형 변환 업데이트로 합쳐서 처리할 수 있다. 이것을 레이지 세그먼트 트리로 처리하는 것은 정확히 수열과 쿼리 13 와 동일하다. 풀이는 이쪽을 참조.
  • HLD와 세그먼트 트리 구축은 O(n)에 가능하고, 경로에 대한 업데이트와 쿼리는 O(log^2n)에, 서브트리에 대한 쿼리와 업데이트는 O(logn)에 처리 가능하다. 총 시간 복잡도는 O(n+qlog^2n)
  • n⇐500,000, q⇐100,000 인데 시간 맞추기가 꽤 타이트하다. Python으로는 TLE가 나고, PyPy로 제출해야 약 8000ms 로 겨우 통과된다,

코드

토론

댓글을 입력하세요:
H T᠎ Q O R
 
ps/problems/boj/17429.txt · 마지막으로 수정됨: 2021/05/28 15:29 저자 teferi