[P4] 백준 18135번 겨울나기 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

리뷰

 

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

오랜만에 풀어본 Lazy Propagation문제, 그룹화 라는 요소가 추가되어 있다.

생각보다 지문이 길어서 문제에 대한 정확한 이해 후에 제출하는 것을 추천한다.

 

 

전역 변수

• N : 산책로 칸의 최대값을 저장하기 위한 정수형 상수 변수
• M : 구역의 최대값을 저장하기 위한 정수형 상수 변수
• n : 산책로 칸의 개수를 저장할 변수
• m : 구역의 개수를 저장할 변수
• lst : 초기 구역의 상태를 저장하기 위한 정수형 배열
• g : 각 산책로 칸의 그룹 번호를 저장하기 위한 정수형 배열
• tree : 세그먼트 트리를 구현하기 위한 정수형 배열
• lazy : 누적 된 업데이트 값을 저장하기 위한 정수형 배열

 

함수

1. build

void build(int node, int s, int e)

 

세그먼트 트리를 초기화 하기 위한 함수

1. 매개변수로 현재 세그먼트 트리의 노드와 탐색 구간 s, e를 전달받는다.
2. 기저 조건으로 리프 노드에 도달했다면 현재 노드에 lst의 탐색 인덱스값을 저장해 준다.
3. 리프 노드가 아니라면 좌우 자식 노드로 재귀를 진행해 준다.
4. 재귀를 빠져나오며 부모 노드의 값을 자식 노드의 값의 합으로 저장해 준다.

---

2. propagate

void propagate(int node, int s, int e)

 

구간에 누적된 업데이트가 있는지 확인한 후 업데이트를 진행하는 함수

1. 매개변수로 노드 정보 node, 탐색 범위 s, e를 전달받는다.
2. 만약 현재 노드에 lazy값이 저장되어 있다면 업데이트를 시작한다.
3. tree의 현재 노드에 탐색 구간 * 저장된 값을 더해준다.
4. 만약 현재 노드가 리프노드가 아니라면 좌우 자식 노드에 lazy값을 더해준다.
5. 업데이트가 진행된 후 현재 노드의 lazy값을 0으로 변경해 준다.

---

3. update

void update(int node, int s, int e, int L, int R, ll val)

 

세그먼트 트리의 노드 값을 업데이트 하기 위한 함수

1. 매개변수로 노드 정보 node, 탐색 범위 s, e, 업데이트 적용 구간 L, R, 업데이트할 값 val를 전달받는다.
2. 매 함수 실행 마다 propagate 함수를 통해 현재 탐색 범위의 누적 업데이트 값이 있다면 적용해 준다.
3. 맵의 범위를 벗어난 경우 바로 리턴 처리해 준다.
4. 탐색 구간이 업데이트 구간에 포함된다면 현재 노드의 lazy값을 val만큼 더해준다.
5. propagate 함수를 통해 현재 구간에 대한 업데이트를 진행한 후 리턴해 준다.
6. 좌우 자식 노드로 재귀적인 탐색을 통해 업데이트를 적용할 구간에 모두 업데이트를 진행해 준다.
7. 재귀를 빠져나오며 부모 노드의 값을 자식 노드 값의 합계로 저장해 준다.

---

4. query

ll query(int node, int s, int e, int L, int R)

 

세그먼트 트리에서 구간의 합을 구하고 리턴하는 함수

1. 매개변수로 노드 정보 node, 탐색 범위 s, e, 구간합을 구할 범위 L, R를 전달받는다.
2. 매 함수 실행 마다 propagate 함수를 통해 현재 탐색 범위의 누적 업데이트 값이 있다면 적용해 준다.
3. 탐색 구간이 구간합을 구할 범위와 겹친다면 현재 노드값을 반환해 준다.
4. 좌우 자식 노드로 재귀를 진행하며 왼쪽 탐색값을 left, 오른쪽 탐색값을 right로 저장한다.
5. left와 right를 합친 값을 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받고, 1부터 m까지의 for문을 개행해 준다.
2. a, b, c에 산책로의 칸과 처음에 할당될 값을 입력 받아준다.
3. g를 활용하여 a부터 b까지의 칸에 현재 구역의 정보를 저장하여 그루핑을 해준다.
4. lst에 현재 구역의 초기값 c를 저장해 준다.
5. build 함수를 통해 세그먼트 트리의 초기화를 진행해 준다.
6. 무한 루프를 실행하고, 매 루프마다 정수형 변수 op에 값을 입력 받아준다.
7. op가 1이라면 산책로 칸 정보 x, y를 입력 받고, 정수형 변수 result를 0으로 초기화 해준다.
8. g에서 x, y의 그룹 정보를 찾아 변수 gx, gy에 할당해 준다.
9. 만약 x가 y보다 작거나 같다면 gx ~ gy 구역의 누적합을 구해준다.
10. x가 y보다 크다면 gx ~ m 구역의 누적합과 1 ~ gy 구역의 누적합을 구해준다.
11. 각 누적합을 result에 더해준 후 result에 저장된 값을 출력해 준다.
12. op가 2라면 산책로 칸 정보 x, y와 더할 값 z를 입력 받아준다.
13. g에서 x, y의 그룹 정보를 찾아 변수 gx, gy에 할당해 준다.
14. x가 y보다 작거나 같다면 gx ~ gy 구역에 z만큼의 값을 더해준다.
15. x가 y보다 크다면 gx ~ m 구역과 1 ~ gy 구역에 z만큼의 값을 더해준다.
16. op가 0이라면 변수 temp에 두번의 값을 추가로 받은 뒤 break 처리해 준다.

 

트러블 슈팅

1. 그루핑 배열 g의 크기를 구역의 최대 크기로 설정했다가 틀렸다, 이후 산책로 칸의 최대 크기로 바꿔주었다.
2. op가 2일 경우 입력 받을 정수 z를 int로 설정하여 무한루프가 발생했다, 이후 long long타입으로 바꿔주었다.

 

참고 사항

• n은 그루핑 시에만 사용되며, 나머지의 경우 m을 기준으로 로직을 작성해야 한다.

 

정답 코드

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

const int N = 2000001;
const int M = 1000001;
int n, m;
int lst[M];
int g[N];
ll tree[M * 4];
ll lazy[M * 4];

void propagate(int node, int s, int e) {
	if (lazy[node]) {
		tree[node] += (e - s + 1) * lazy[node];
		if (s != e) {
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
}

void update(int node, int s, int e, int L, int R, ll val) {
	propagate(node, s, e);
	if (R < s || e < L) return;
	if (L <= s && e <= R) {
		lazy[node] += val;
		propagate(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, val);
	update(node * 2 + 1, mid + 1, e, L, R, val);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

ll query(int node, int s, int e, int L, int R) {
	propagate(node, s, e);
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	ll left = query(node * 2, s, mid, L, R);
	ll right = query(node * 2 + 1, mid + 1, e, L, R);
	return left + right;
}

void build(int node, int s, int e) {
	if (s == e) tree[node] = lst[s];
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

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

	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int a, b, c; cin >> a >> b >> c;
		for (int j = a; j <= b; ++j) g[j] = i;
		lst[i] = c;
	}

	build(1, 1, m);

	while (1) {
		int op; cin >> op;
		if (op == 1) {
			int x, y; cin >> x >> y;
			ll result = 0;
			int gx = g[x], gy = g[y];
			if (x <= y) result += query(1, 1, m, gx, gy);
			else {
				result += query(1, 1, m, gx, m);
				result += query(1, 1, m, 1, gy);
			}
			cout << result << "\n";
		}
		else if (op == 2) {
			int x, y; cin >> x >> y;
			ll z; cin >> z;
			int gx = g[x], gy = g[y];
			if (x <= y) update(1, 1, m, gx, gy, z);
			else {
				update(1, 1, m, gx, m, z);
				update(1, 1, m, 1, gy, z);
			}
		}
		else {
			int temp; cin >> temp >> temp;
			break;
		}
	}
}