취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18135번 문제인 겨울나기이다.
문제는 아래 링크를 확인하자.

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

주어지는 각 칸과 영역에 대하여 각 칸이 어느 영역에 포함되어있는지를 나타내는 배열을 하나 만들자. 그러면 주어진 문제는 영역들의 관점에서 보아, 일차원 배열 위에서의 구간 업데이트와 구간 합 쿼리를 지원하는 자료구조를 이용해 해결할 수 있게 변형됨을 쉽게 관찰할 수 있다.

lazy propagation을 지원하는 구간 합 segment tree를 이용해 문제를 해결해주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, M;
int id[2000001];
ll arr[1000001];
ll seg[2097153];
ll lazy[2097153];

void prop(int L, int R, int sI) {
	seg[sI] += lazy[sI] * (R - L + 1);
	if (L < R) lazy[sI * 2] += lazy[sI], lazy[sI * 2 + 1] += lazy[sI];
	lazy[sI] = 0;
}

ll init(int L, int R, int sI) {
	if (L < R) return seg[sI] = init(L, (L + R) / 2, sI * 2) + init((L + R) / 2 + 1, R, sI * 2 + 1);
	else return seg[sI] = arr[L];
}

ll rupd(int L, int R, int qL, int qR, ll qVal, int sI) {
	if (lazy[sI]) prop(L, R, sI);
	if (qR < L || R < qL) return seg[sI];
	if (qL <= L && R <= qR) {
		lazy[sI] += qVal;
		prop(L, R, sI);
		return seg[sI];
	}
	return seg[sI] = rupd(L, (L + R) / 2, qL, qR, qVal, sI * 2) + rupd((L + R) / 2 + 1, R, qL, qR, qVal, sI * 2 + 1);
}

ll rsum(int L, int R, int qL, int qR, int sI) {
	if (lazy[sI]) prop(L, R, sI);
	if (qR < L || R < qL) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return rsum(L, (L + R) / 2, qL, qR, sI * 2) + rsum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int m = 1; m <= M; m++) {
		int a, b; ll c; cin >> a >> b >> c;
		arr[m] = c;
		if (a <= b) {
			for (int i = a; i <= b; i++) id[i] = m;
		}
		else {
			for (int i = a; i <= N; i++) id[i] = m;
			for (int i = 1; i <= b; i++) id[i] = m;
		}
	}

	init(1, M, 1);

	int q, x, y, z;
	cin >> q;
	while (q) {
		if (q == 1) {
			cin >> x >> y;
			x = id[x], y = id[y];
			if (x <= y) cout << rsum(1, M, x, y, 1) << '\n';
			else cout << rsum(1, M, x, M, 1) + rsum(1, M, 1, y, 1) << '\n';
		}
		else {
			cin >> x >> y >> z;
			x = id[x], y = id[y];
			if (x <= y) rupd(1, M, x, y, z, 1);
			else {
				rupd(1, M, x, M, z, 1), rupd(1, M, 1, y, z, 1);
			}
		}
		cin >> q;
	}
}