[ BOJ ] 2934 : LRH 식물 ( PLATINUM 4 ) / C

문제

상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다.

상근이는 매일 매일 화단에 식물을 하나씩 심는다. 첫 번째 날에 심은 식물의 높이는 1이고, 그 다음날에 심은 식물은 전날에 심은 식물의 높이보다 1 크다.

새 식물의 줄기가 다른 식물의 수평 선분과 교차하는 경우가 있다. 이러한 경우에 그 위치에는 꽃이 하나 피게 된다. (이미 꽃이 있는 경우에는 꽃이 더 피지 않는다) 점에서 접하는 경우에는 꽃이 피지 않는다.

아래 그림은 예제를 나타낸 것이다.

모든 식물의 좌표가 주어졌을 때, 매일 매일 피는 꽃의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 식물을 심은 날의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

다음 N개 줄에는 매일 매일 심은 식물의 두 줄기 좌표 L과 R이 주어진다. (1 ≤ L < R ≤ 100,000) 

출력

총 N개의 줄에 매일 매일 핀 꽃의 수를 출력한다.

풀이 과정

느리게 갱신되는 세그먼트 트리 알고리즘을 이용하면 쉽게 풀 수 있다.

식물이 자라는 L, R 사이에서, 꽃이 필 수 있는 곳인 L+1 ~ R-1 에 1을 증가시키고, L과 R 지점에서 이 위치의 식물 갯수를 구하고 0으로 갱신한다.

즉, tree에는 기존에 얼마나 식물이 자랐는지 ( 이곳에 얼마나 꽃을 피울 수 있는지 ) 를 저장해서, L, R 지점의 노드만 가져와 꽃을 피운 후 그 지점을 0으로 갱신해준다. 한 번 식물이 자랄 때 연속된 구간에 자라기 때문에 구간을 한번에 업데이트하는 lazy가 필요하다.

#include <stdio.h>
#define SIZE 100001
typedef long long LL;

LL arr[SIZE] = {0,};
LL tree[SIZE * 4] = {0,};
LL lazy[SIZE * 4] = {0,};

void update_lazy(int start, int end, int idx) {
	if (lazy[idx] != 0) {
		tree[idx] += (end - start + 1) * lazy[idx];
		if (start != end) {
			lazy[idx * 2] += lazy[idx];
			lazy[idx * 2 + 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

void update_range(int start, int end, int idx, int left, int right) {
	update_lazy(start, end, idx);
	if (end < left || right < start) return;
	if (left <= start && end <= right) {
		tree[idx] += (end - start + 1);
		if (start != end) {
			lazy[idx * 2] += 1;
			lazy[idx * 2 + 1] += 1;
		}
		return;
	}

	int mid = (start + end) / 2;
	update_range(start, mid, idx * 2, left, right);
	update_range(mid + 1, end, idx * 2 + 1, left, right);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

void update_point(int start, int end, int idx, int what) {
	update_lazy(start, end, idx);

	if (what < start || end < what) return;
	if (start == end) {
		tree[idx] = 0;
		return;
	}

	int mid = (start + end) / 2;
	update_point(start, mid, idx * 2, what);
	update_point(mid + 1, end, idx * 2 + 1, what);
	tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

LL getVal(int start, int end, int idx, int what) {
	update_lazy(start, end, idx);

	if (what < start || end < what) return 0;
	if (start == end) return tree[idx];

	int mid = (start + end) / 2;
	return getVal(start, mid, idx * 2, what) + getVal(mid + 1, end, idx * 2 + 1, what);
}

int main(void) {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d %d", &l, &r);
		if (l + 1 < r) update_range(0, SIZE - 1, 1, l, r - 2);
		LL cnt = getVal(0, SIZE - 1, 1, l - 1) + getVal(0, SIZE - 1, 1, r - 1);
		printf("%lld\n", cnt);

		update_point(0, SIZE - 1, 1, l - 1);
		update_point(0, SIZE - 1, 1, r - 1);
	}
	return 0;
}