사용자 도구

사이트 도구


ps:problems:boj:13925

수열과 쿼리 13

ps
링크https://www.acmicpc.net/problem/13925
출처BOJ
문제 번호13925
문제명수열과 쿼리 13
레벨다이아몬드 5
분류

구간 쿼리

시간복잡도O(n+mlogn)
인풋사이즈n<=100,000, m<=100,000
사용한 언어PyPy
제출기록170564KB / 1072ms
최고기록1072ms
해결날짜2021/03/26

풀이

  • 구간 업데이트와 구간합 쿼리가 들어오는 문제이긴 한데, 단순히 세그먼트 트리와 lazy propagation를 이용해서 구현하기에는 업데이트 쿼리의 종류가 다양하다.
  • 업데이트를, x := ax+b 의 선형변환이라고 생각하면, 곱 업데이트는 (a,0), 합 업데이트는 (1,b), assignment 업데이트는 (0,b)로 생각해서 모두 처리할 수 있다.
  • 구간에 대해서 선형변환을 적용하는 것은 (ax1+b) + (ax2+b) + … + (axn+b) = a(x1+x2+…+xn) + b*n 으로 처리된다
  • 선형변환을 컴포지션하는것은 c(ax+b)+d = (a*c)x + (bc+d) 로 처리된다
  • 이 결과를 갖고 lazy propagation에서 사용한 노테이션대로, f,g,h 를 정의하면
    • f(x,y) = x + y
    • g(x, (a,b), size) = a*x + b*size
    • h( (a1,b1), (a2,b2)) = (a1*b1, a2*b1+b2)
  • 이것만 정리되면 나머지는 그냥 세그먼트 트리를 사용하기만 하면 된다. 시간 복잡도는 세그먼트 트리를 구축하는 데에 O(n), m개의 쿼리를 각각 O(logn)에 처리하는 데에 O(mlogn), 합쳐서 O(n+mlogn)이다

코드

(다이아몬드 이상은 코드 생략)

토론

댓글을 입력하세요:
F L E V P
 
ps/problems/boj/13925.txt · 마지막으로 수정됨: 2021/04/30 15:13 저자 teferi