[BOJ] 수열과 쿼리 13

 

 

www.acmicpc.net/problem/13925

13925번: 수열과 쿼리 13

알고리즘: Segtree, Lazy propagation

시간복잡도: $O((N+M)logN)$

---

1, 2번 쿼리를 보면 구간에 있는 모든 원소에 특정 값을 연산한다.

따라서, Lazy propatagion을 써야한다는 것을 알 수 있다.'

 

1, 2번 쿼리를 통해 $a\rightarrow ax+b$로 바꼈다고 생각해보자

여기다가 다시 p를 곱하고 q를 더하면,

$ax+b\rightarrow p(ax+b)+q=pax+(pb+q)$

$a\rightarrow pa,\ b\rightarrow pb+q$

 

a = lazy1, b = lazy2로 관리해주되,

위의 식처럼 곱하는 연산에서는 a, b 값 모두 변화시켜줘야 한다는 점을 유의해야 한다.