Lazypropagation
-
[BOJ] 수열과 쿼리 13PS/BOJ 2020. 10. 23. 22:43
www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net 알고리즘: Segtree, Lazy propagation 시간복잡도: $O((N+M)logN)$ 1, 2번 쿼리를 보면 구간에 있는 모든 원소에 특정 값을 연산한다. 따라서, Lazy propatagion을 써야한다는 것을 알 수 있다.' 1, 2번 쿼리를 통해 $a\rightarrow ax+b$로 바꼈다고 생각해보..