수열과 쿼리 13

• 구간 업데이트와 구간합 쿼리가 들어오는 문제이긴 한데, 단순히 세그먼트 트리와 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)이다

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

• Dependency: teflib.segmenttree.LazySegmentTree