[자료구조] 백준 13925번: 수열과 쿼리 13 (C++), 첫 다이아 문제

https://www.acmicpc.net/problem/13925

13925번: 수열과 쿼리 13

한 문제만 풀면 플레티넘이라서 멋지게 피날레를 장식하고 싶은 마음에 풀 수 있을 거 같은 다이아 문제를 골랐었다.

(그러지 말 걸 그냥 플레 문제 2개 더 풀걸)

다이아다 보니 당연히 어려웠고, 아 이게 다이아인가 싶었다.

---

우선 쿼리의 종류는 4가지다.

1.  x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y)
2.  x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y)
3.  x y v: Ai = v를 수행한다. (x ≤ i ≤ y)
4.  x y: (ΣAi) % MOD를 출력한다. (x ≤ i ≤ y)

4번 쿼리를 보면 구간 합을 구해야 하는 것을 짐작할 수 있다.

하지만, 수열의 크기가 100,000(n)으로 주어질 수 있고, 쿼리가 100,000개(m)로 주어질 수 있으니

O(n*m)을 피하는 세그먼트 트리(m*logn)로 문제를 접근해야 한다.

 

그리고, 1~3번 쿼리를 보면 구간 업데이트를 해야 한다.

일반적인 세그먼트 트리는 구간 업데이트를 하면 O(nlogn)으로 Lazy Propagation(logn)으로 해결해야 한다.

 

그런데 이번 문제에서 제일 어렵다고 느낀 포인트는 1~3번 쿼리 별로 역할이 나뉘는 부분 때문인데

이때까지는 세그먼트 트리라면 한 가지 역할을 해내는 트리를 구성해왔었다.

하지만, 이번에 만들 세그먼트 트리는 3가지 역할을 소화해내야 한다.

그만큼 세그먼트 트리와 Lazy Propagation에 대해 정확히 이해하고 있어야 한다.

---

lazy 배열을 하나만 선언하면 안 된다고 생각했다.

lazyUpdate를 했을 때 하나의 배열에서 어떤 값은 곱해주는 거고 어떤 값은 더해주는 걸 구별해야 하기 때문에

>> 각 역할 별로 lazy 배열을 두 개 선언해줬다.

ll lazyAdd[MAX * 4];
ll lazyMul[MAX * 4];

---

풀면서 느낀 이 부분이 이번 문제의 포인트

'어떤 노드를 사용하기 위해 update 해야 하는 순간이 올 때 어떻게 처리할 것인가?'가 이번 문제에서 최종적으로 요구하는 문제였다.

>> 정확히 얘기하면 해당 노드는 계산식을 세우기 쉽지만 propagate 되는 lazy값들을 자식 노드가 어떻게 처리할 것인지를 묻는 문제다.

 

조금 쉽게 이해하기 위해 미지수 value를 두고 얘기해보자. (value = propagate 받는 자식 노드를 얘기)

Lazy Propagation의 특성상 업데이트할 값(곱할 값 (mul), 더할 값 (add))이 밀려있다고 하자.

첫 업데이트가 곱할 값, 두 번째 업데이트가 더할 값이라고 치면

value는 mul * value + add가 된다.

이번엔 반대로 첫 업데이트가 더할 값, 두 번째 업데이트가 곱할 값이라고 치면

value는 (add + value) * mul가 된다. >> 이게 젤 중요

 

즉, 곱할 값이 먼저 와있다면 노드의 곱하기 lazy는 이런 식으로 전염을 받고

lazyMul[node] = lazyMul[node] * lazyMul[parentNode] % MOD;

더하기 이후에 곱하기가 온다면 더할 값에도 곱할 값을 곱해주어야 한다는 것이 이번 문제의 핵심이다.

lazyAdd[node] = ((lazyAdd[node] * lazyMul[parentNode]) + lazyAdd[parentNode]) % MOD;

 

그리고, lazyUpdate를 해야 하는 상황이 온다면 세그 트리 해당 노드의 계산은 이런 식으로 처리가 된다.

sgTree[node] = ((sgTree[node] * lazyMul[node] % MOD) +
			 ((end - start + 1) * lazyAdd[node]) % MOD) % MOD;

---

3번 쿼리는 방금 내용들을 응용의 느낌으로 곱하기 lazy에 0이 담겨있고, 더하기 lazy에 바꿔줄 v가 담겨있다면

해당 구간의 노드 값들은 전부 v로 바뀌게 된다.

>> 기존의 값 * 0 + 바꿔줄 값 v

---

[AC 코드]

설명은 따로 안 해두었지만, 당연히 곱하기 lazy의 초기값들은 1로 되어있어야 한다. 어떤 값이든 1을 곱해야 항등원이기 때문이다.

#include <iostream>
#define ll long long
#define MAX (100000 + 1)
#define MOD (1000000007)
using namespace std;

ll arr[MAX];
ll sgTree[MAX * 4];
ll lazyAdd[MAX * 4];
ll lazyMul[MAX * 4];
int n;

ll sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = arr[start];
	}
	int mid = (start + end) >> 1;
	return sgTree[node] = (sgInit(start, mid, node * 2) + 
		sgInit(mid + 1, end, node * 2 + 1)) % MOD;
}

void lazyUpdate(int start, int end, int node) {
	if (lazyAdd[node] != 0 || lazyMul[node] != 1) {
		sgTree[node] = ((sgTree[node] * lazyMul[node] % MOD) +
			 ((end - start + 1) * lazyAdd[node]) % MOD) % MOD;

		if (start != end) {
			lazyAdd[node * 2] = ((lazyAdd[node * 2] * lazyMul[node]) + lazyAdd[node]) % MOD;
			lazyMul[node * 2] = lazyMul[node * 2] * lazyMul[node] % MOD;
			lazyAdd[node * 2 + 1] = ((lazyAdd[node * 2 + 1] * lazyMul[node]) + lazyAdd[node]) % MOD;
			lazyMul[node * 2 + 1] = lazyMul[node * 2 + 1] * lazyMul[node] % MOD;
		}

		lazyAdd[node] = 0;
		lazyMul[node] = 1;
	}
}

void update(int start, int end, int node, int left, int right, ll add, ll mul) {
	lazyUpdate(start, end, node);
	if (end < left || right < start) return;

	if (left <= start && end <= right) {
		lazyAdd[node] = ((lazyAdd[node] * mul % MOD) + add) % MOD;
		lazyMul[node] = lazyMul[node] * mul % MOD;
		lazyUpdate(start, end, node);
		return;
	}

	int mid = (start + end) >> 1;
	update(start, mid, node * 2, left, right, add, mul);
	update(mid + 1, end, node * 2 + 1, left, right, add, mul);
	sgTree[node] = (sgTree[node * 2] + sgTree[node * 2 + 1]) % MOD;
	return;
}

ll query(int start, int end, int node, int left, int right) {
	lazyUpdate(start, end, node);
	if (left > end || right < start) return 0;
	if (left <= start && end <= right) {
		return sgTree[node] % MOD;
	}

	int mid = (start + end) >> 1;
	return (query(start, mid, node * 2, left, right) + 
		query(mid + 1, end, node * 2 + 1, left, right)) % MOD;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	sgInit(1, n, 1);

	// lazyMul 구간 곱 1로 초기화
	for (int i = 1; i <= 4 * n; i++) {
		lazyMul[i] = 1;
	}

	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int q;
		cin >> q;
		if (q == 1) {
			// plus
			int x, y;
			ll v;
			cin >> x >> y >> v;
			update(1, n, 1, x, y, v, 1);
		}
		else if (q == 2) {
			// multiply
			int x, y;
			ll v;
			cin >> x >> y >> v;
			update(1, n, 1, x, y, 0, v);
		}
		else if (q == 3) {
			// change
			int x, y;
			ll v;
			cin >> x >> y >> v;
			update(1, n, 1, x, y, v, 0);
		}
		else {
			int x, y;
			cin >> x >> y;
			cout << query(1, n, 1, x, y) % MOD << '\n';
		}
	}
	return 0;
}