[BOJ] 백준 13925. 수열과 쿼리 13 (Diamond V)

고인물들 사이에선 웰노운이라길래 풀어봤는데,

엄청 어렵진 않지만, 이게 어떻게 웰노운인가... 싶은 문제.

처음 문제를 보면 단순 레이지세그를 돌리면 되는거 아닌가 싶어 쉽게 생각했는데, 그렇지 않다.

문제는 아래와 같다.

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

13925번: 수열과 쿼리 13

---

의식의 흐름 및 해설

처음에는 단순히 update_lazy를 두 개 만들어서 하나는 곱셈, 하나는 덧셈용으로 잘 쓰면 되지 않을까 싶어 쉽게 생각했다. 그러나, 조금만 생각해보면 곱셈이 덧셈에 영향을 줌을 알 수 있다.

예를 들어, 4라는 수에 3을 더하고 4를 곱하면 지금에서야 숫자 하나에만 덧셈과 곱셈을 적용하니 문제가 없지만, 구간에서의 update를 적용할 때, 나중에 더한 숫자를 한꺼번에 처리하는 레이지세그 특성 상, 덧셈과 곱셈 순서가 엉켜 제대로 계산되지 않는다.

 

배열 [A, B, C]가 있다고 하자.

 

여기서 2~3번째 구간에 3씩 더한다고 하면 아래와 같이 될 것이다.

 

[A, B+3, C+3]

 

여기서 1~3번째 구간에 2씩 곱한다고 하면 아래와 같이 될 것이다.

 

[2*A, 2(B+3), 2(C+3)]

 

여기서 1~3번째 구간에 4씩 더한다고 하면 아래와 같이 될 것이다.

 

[2*A+4, 2(B+3)+4, 2(C+3)+4]

 

만약 덧셈 레이지세그만 존재한다면 3씩 더하고, 4씩 더한 후, 나중에 쿼리가 요청될 때 레이지에 누적된 7의 값을 한꺼번에 더해서 출력하겠지만, 곱셈과 덧셈이 함께 있으면 불가능하다. 위의 예시를 보면 알겠지만, 곱셈의 레이지세그가 덧셈의 레이지세그에 영향을 주기 때문이다.

 

따라서 레이지세그를 아래와 같이 만들어주자.

struct Tree {
	ll val, lazy[2] = {1, 0};
};

lazy값이 2개이며, lazy[0]은 곱셈 레이지세그, lazy[1]은 덧셈 레이지세그이다.

 

void update_lazy(int node, int s, int e) {
	if (tree[node].lazy[0]!=1) {
		tree[node].val *= tree[node].lazy[0];
		tree[node].val %= MOD;
		if (s != e) {
			ll k = tree[node].lazy[0];
			tree[node * 2].lazy[0] *= k;
			tree[node * 2].lazy[1] *= k;
			tree[node * 2].lazy[0] %= MOD; tree[node * 2].lazy[1] %= MOD;
			tree[node * 2 + 1].lazy[0] *= k;
			tree[node * 2 + 1].lazy[1] *= k;
			tree[node * 2 + 1].lazy[0] %= MOD; tree[node * 2 + 1].lazy[1] %= MOD;
		}
		tree[node].lazy[0] = 1;
	}
	if (tree[node].lazy[1]) {
		tree[node].val += (1LL * e - s + 1) * tree[node].lazy[1];
		tree[node].val %= MOD;
		if (s != e) {
			ll k = tree[node].lazy[1];
			tree[node * 2].lazy[1] += k;
			tree[node * 2].lazy[1] %= MOD;
			tree[node * 2 + 1].lazy[1] += k;
			tree[node * 2 + 1].lazy[1] %= MOD;
		}
		tree[node].lazy[1] = 0;
	}
}

덧셈 레이지세그는 (e-s+1)을 곱해주지만, 구간합 세그먼트트리에서의 곱셈 레이지세그는 lazy를 곱해주기만 하면 구간합에 곱한 값이 잘 적용된다. (뭐라 말을 해야될지 모르겠는데, 곱셈의 성질과 덧셈의 성질을 잘 생각해주면 된다.)

 

나머지는 일반 레이지세그처럼 잘 적용하면 된다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 100011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const ll MOD = 1e9 + 7;
ll N, M, a[MAX];
struct Tree {
	ll val, lazy[2] = {1, 0};
};
Tree tree[1 << 18];
void update_lazy(int node, int s, int e) {
	if (tree[node].lazy[0]!=1) {
		tree[node].val *= tree[node].lazy[0];
		tree[node].val %= MOD;
		if (s != e) {
			ll k = tree[node].lazy[0];
			tree[node * 2].lazy[0] *= k;
			tree[node * 2].lazy[1] *= k;
			tree[node * 2].lazy[0] %= MOD; tree[node * 2].lazy[1] %= MOD;
			tree[node * 2 + 1].lazy[0] *= k;
			tree[node * 2 + 1].lazy[1] *= k;
			tree[node * 2 + 1].lazy[0] %= MOD; tree[node * 2 + 1].lazy[1] %= MOD;
		}
		tree[node].lazy[0] = 1;
	}
	if (tree[node].lazy[1]) {
		tree[node].val += (1LL * e - s + 1) * tree[node].lazy[1];
		tree[node].val %= MOD;
		if (s != e) {
			ll k = tree[node].lazy[1];
			tree[node * 2].lazy[1] += k;
			tree[node * 2].lazy[1] %= MOD;
			tree[node * 2 + 1].lazy[1] += k;
			tree[node * 2 + 1].lazy[1] %= MOD;
		}
		tree[node].lazy[1] = 0;
	}
}
ll init(int node, int s, int e) {
	if (s == e)
		return tree[node].val = a[s];
	int mid = (s + e) / 2;
	return tree[node].val = (init(node * 2, s, mid)
		+ init(node * 2 + 1, mid + 1, e)) % MOD;
}
ll query(int node, int s, int e, int left, int right) {
	update_lazy(node, s, e);
	if (e < left || right < s)
		return 0;
	if (left <= s && e <= right)
		return tree[node].val % MOD;
	int mid = (s + e) / 2;
	return (query(node * 2, s, mid, left, right)
		+ query(node * 2 + 1, mid + 1, e, left, right)) % MOD;
}
void update_plus(int node, int s, int e, int left, int right, ll diff) {
	update_lazy(node, s, e);
	if (e < left || right < s)
		return;
	if (left <= s && e <= right) {
		tree[node].lazy[0] = 1;
		tree[node].lazy[1] += diff;
		tree[node].lazy[1] %= MOD;
		update_lazy(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update_plus(node * 2, s, mid, left, right, diff);
	update_plus(node * 2 + 1, mid + 1, e, left, right, diff);
	tree[node].val = (tree[node * 2].val + tree[node * 2 + 1].val) % MOD;
}
void update_multi(int node, int s, int e, int left, int right, ll diff) {
	update_lazy(node, s, e);
	if (e < left || right < s)
		return;
	if (left <= s && e <= right) {
		tree[node].lazy[0] = diff;
		tree[node].lazy[1] = 0;
		update_lazy(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update_multi(node * 2, s, mid, left, right, diff);
	update_multi(node * 2 + 1, mid + 1, e, left, right, diff);
	tree[node].val = (tree[node * 2].val + tree[node * 2 + 1].val) % MOD;
}
void update(int node, int s, int e, int left, int right, ll val) {
	update_lazy(node, s, e);
	if (e < left || right < s)
		return;
	if (left <= s && e <= right) {
		tree[node].lazy[0] = 0;
		tree[node].lazy[1] = val;
		update_lazy(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, left, right, val);
	update(node * 2 + 1, mid + 1, e, left, right, val);
	tree[node].val = (tree[node * 2].val + tree[node * 2 + 1].val) % MOD;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	init(1, 1, N);
	cin >> M;
	while (M--) {
		int ch, x, y;
		ll v;
		cin >> ch >> x >> y;
		if (ch == 1) {
			cin >> v;
			update_plus(1, 1, N, x, y, v);
		}
		else if (ch == 2) {
			cin >> v;
			update_multi(1, 1, N, x, y, v);
		}
		else if (ch == 3) {
			cin >> v;
			update(1, 1, N, x, y, v);
		}
		else {
			cout << query(1, 1, N, x, y) % MOD << "\n";
		}
	}
}

 update_plus, update_multi, update를 하나의 update 코드로 정리하고, 파라미터로 다른 값을 넘겨주는 방식으로 코드양을 확 줄일 수 있는 모양이다.

---

레이지 세그를 여러 개 관리하면서 사칙연산 성질을 이용하는 어려운 문제였다.

세그먼트는 진짜 활용 방법이 굉장히 다양한듯...