oVeron

덧셈 쿼리와 곱셈 쿼리를 어떻게 같이 수행할 지 묻는 문제이다. lazy 배열을 세그먼트 트리에 곱셈할 수, 덧셈할 수 두 개로 나누어 pair 형태로 저장하면 문제를 해결할 수 있다. 식으로 표현하면 대략 아래와 같다. \(lazy[i] = (a, b)\)\(a * segTree[i] + b\) 이런 식으로 lazy 배열을 표현하면 모든 쿼리를 편리하게 수행할 수 있다.1번 쿼리 : 수를 더하는 연산이므로 \(b\)에다 \(v\)를 더하면 된다.2번 쿼리 : 수를 곱하는 연산이다. \(a, b\)모두에 \(v\)를 곱해주면 된다.3번 쿼리 : 수를 \(v\)로 변환하는 연산이다. \(a = 0, b = v\)로 바꿔주면 된다.4번 쿼리 : 구간의 합을 구하면 된다. 다만, lazy 배열에 값을 밀어넣을..

알고리즘/baekjoon 2024. 7. 20. 09:46