c언어 18437번 회사 문화 5 (백준)

#include <stdio.h>
#include <stdlib.h>

int tree[266000]={}, start[100001]={}, end[100001]={}, ETT=0;
char lazy[266000]={};

typedef struct list{ //단방향 리스트
	struct list * next;
	int val;
}list;

void insert(int x, int y, list vec[]) { //리스트 삽입
	list * newNode = (list*) malloc(sizeof(list));
	newNode->val = y;
	newNode->next = vec[x].next;
	vec[x].next = newNode;
	return;
}

void dfs(int x, list vec[]) { //ETT
	start[x] = ++ETT;
	for(list *p=vec[x].next; p!=NULL; p=p->next) dfs(p->val, vec);
	end[x] = ETT;
	return;
}

void lazyU(int s, int e, int node) { //미룬거 수정
	if(lazy[node]) {
		if(lazy[node] == 1) tree[node] = e-s+1;
		else if(lazy[node] == 2) tree[node] = 0;
		
		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) { //수정
	lazyU(s,e,node); //미룬거 수정
	if(s>r || e<l) return; //범위 밖
	if(l<=s && e<=r) { //범위에 속함
		if(dif == 1) tree[node] = e-s+1;
		else if(dif == 2) tree[node] = 0;
		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 l, int r) { //찾기
	lazyU(s,e,node);
	if(s>r || e<l) return 0;
	if(l<=s && e<=r) return tree[node];
	int m=(s+e)/2;
	return find(s,m,node*2,l,r) + find(m+1,e,node*2+1,l,r);
}

int main(void) {
	int n,m,tmp;
	scanf("%d",&n); //입력
	//리스트로 구현한 벡터 (...)
	list * vec = (list*) malloc(sizeof(list) * (n+1));
	
	for(int i=1; i<=n; i++) { //입력
		vec[i].next = NULL;
		scanf("%d",&tmp);
		if(tmp != 0) insert(tmp, i, vec);//벡터에 삽입	
	}
	
	dfs(1,vec); //ETT
	
	scanf("%d",&m); //입력
	update(1,n,1,start[1],end[1],1); //초기상태는 전부 불이 켜져 있다.
	
	while(m--) { //query
		int a,b;
		scanf("%d %d",&a,&b);
		if(a==3) { //find, 상사 자신은 빼주어야 한다.
			printf("%d\n",find(1,n,1,start[b],end[b])-find(1,n,1,start[b],start[b]));
		} else { //update, 상사의 자식노드들을 갱신한다.
			for(list*p=vec[b].next;p!=NULL;p=p->next) {
				update(1,n,1,start[p->val],end[p->val],a);
			}
		}
	}
}

 

풀이 : lazy propagation, euler track trick

 

회사문제 2와 달리 누적합이 아니라, 그냥 1또는 0의 값만 가질 수 있으며, 찾고자 하는 구간에서 1이 몇개인지를 출력하는 문제입니다.

 

그래서 += 가 아니라 = 을 사용해야 합니다.

 

1. 그래프이므로 ETT 을 사용하여 segment tree에 활용할 수 있도록 시작번호, 종료번호를 붙여줍니다.

 

2. 문제에서 주어진 초기값은 모든 회사원의 컴퓨터가 불이 켜져 있으므로 그래프의 root을 가지고 전부 켜져있는 상태(1)로 만들어 줍니다.

 

3. query 처리에서

 

3.1 값을 얻어오는 경우, 자신을 제외한 부하들의 켜져있는 컴퓨터의 개수를 물어보기에, 자신을 포함한 상태로 찾은 다음, 자기 자신의 상태를 빼주면 됩니다.

 

3.2 값을 수정하는 경우, 자신을 제외한 부하들의 상태를 수정하는 것이므로, 자신과 바로 연결되어 있는 자식노드들을 서브 트리의 root로 바라보면서 update을 해줍니다.

 

 

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