====== 수열과 쿼리 13 ======

===== 풀이 =====
  * 구간 업데이트와 구간합 쿼리가 들어오는 문제이긴 한데, 단순히 세그먼트 트리와 [[ps:세그먼트 트리#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) 로 처리된다
  * 이 결과를 갖고 [[ps:세그먼트 트리#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)이다

===== 코드 =====
(다이아몬드 이상은 코드 생략)
  * Dependency: [[:ps:teflib:segmenttree#LazySegmentTree|teflib.segmenttree.LazySegmentTree]]

{{tag>BOJ ps:problems:boj:다이아몬드_5}}