글 읽기 - 레이지 프로퍼게이션에 대한 질문입니다.

jh20s 6년 전 0

8889번 등고선 지도, 3392 화성지도를 풀면 레이지 프로퍼게이션을 공부해서 해결을 했는데

만약 "일정 범위를 어떤 수로 update 할 때 주어진 L,R범위에서 리프노드가 1이상의 개수를 출력하라" 이런 것은 어떻게 코드를 짜야하나요?

그냥 세그먼트트리를 이용하면 쉽게 할 수 있는데,

레이지 프로퍼게이션으로 하려하니 도저히 모르겠네요 ㅠㅠ...

코드는 제가 등고선 지도를 풀 때 사용한 레이지프로퍼게이션 코드입니다.

vector<int> seg;
vector<int> lazy;
int h = 1;
void propagate(int L, int R, int num) {
	if (lazy[num] != 0) {
		if (num < h) {
			lazy[num * 2] += lazy[num];
			lazy[num * 2 + 1] += lazy[num];
		}
		seg[num] += lazy[num];
		lazy[num] = 0;
	}
}

void update(int L, int R, int nodeNum, int nodeL, int nodeR,int state) {
	propagate(nodeL, nodeR, nodeNum);
	if (L <= nodeL&&nodeR <= R) {
		lazy[nodeNum] += state;
		propagate(nodeL,nodeR,nodeNum);
		return;
	}
	if (nodeR < L || R < nodeL) return;
	int mid = (nodeL + nodeR) / 2;
	update(L, R, nodeNum * 2, nodeL, mid, state), update(L, R, nodeNum * 2 + 1, mid + 1, nodeR, state);
	if(nodeNum<h)
		seg[nodeNum] = max(seg[nodeNum * 2], seg[nodeNum * 2 + 1]);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

레이지 프로퍼게이션에 대한 질문입니다.

jh20s 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말