c언어 2934번 LRH 식물 (백준)

#include <stdio.h>

int tree[400004] = {};
int lazy[400004] = {};

void lazyUpdate(int s, int e, int node) { //미룬거 처리
	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;
	return;
}

void update(int s, int e, int node, int l, int r, int dif) { //구간 수정
	lazyUpdate(s,e,node);
	if(s>r || e<l) return; //범위 벗어남
	if(l<=s && e<=r) { //범위에 속함
		tree[node]+=(e-s+1)*dif;
		if(s!=e) {
			lazy[node*2]+=dif;
			lazy[node*2+1]+=dif;
		} return;
	}
	//범위에 걸친 경우
	int m=(s+e)/2;
	update(s,m,node*2,l,r,dif);
	update(m+1,e,node*2+1,l,r,dif);
	tree[node] = tree[node*2]+tree[node*2+1];
	return;
}

int find(int s, int e, int node, int index) { //단일 탐색
	lazyUpdate(s,e,node);
	if(s>index || e<index) return 0; //범위 벗어남
	if(s==e) {
		if(s==index) return tree[node];
		else return 0;
	}
	int m=(s+e)/2;
	return find(s,m,node*2,index) + find(m+1,e,node*2+1,index);
}

int main(void) {
	int n;
	scanf("%d",&n);
	while(n--) { //쿼리
		int a,b,c,d;
		scanf("%d %d",&a,&b);
		c = find(1,100000,1,a);
		d = find(1,100000,1,b);
		printf("%d\n",c+d);
		update(1,100000,1,a+1,b-1,1);
		update(1,100000,1,a,a,-c);
		update(1,100000,1,b,b,-d);
	}
}

 

풀이 : 느리게 갱신되는 세그먼트 트리, lazy propagation

 

1. 세그먼트 트리, lazy propagation을 위한 배열을 준비합니다.

2. 구간은 1~100000입니다.

3. 쿼리로 두 수 가 입력되고 이를 a,b 라 할 때, a번, b번에 꽃이 될수 있는 것이 몇개 인지를 각각 구한 다음 더해서 출력합니다.

4. a+1, b-1까지 꽃이 생길 수 있다는 것을 더해줍니다. (+1)

5. a, b 각각 꽃이 생길 수 있는것을 3에서 구한 꽃의 개수 만큼 빼줍니다. (- 생성된 꽃의 개수)

 

주의 : 범위는 1~100000 입니다. 줄기는 꽃이 될 수 없습니다! 고로 +1 을 해줄 범위는 a~b가 아니라 a+1~b-1 입니다.

 

추가 : 펜윅트리로 구현한다면 메모리도, 시간도 더욱 효율적으로 할 수 있습니다.