c언어 14287번 회사 문화 3 (백준)

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

int tree[266000] = {}, ETT=0;

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

void update(int s, int e, int node, int index, int dif) { //단일 수정
	if(s>index || e<index) return; //범위 벗어남
	if(s==e) { //범위에 속함
		if(s==index) tree[node] += dif;
		return;
	}
	int m=(s+e)/2; //범위에 걸치면 하위 노드로
	update(s,m,node*2,index,dif);
	update(m+1,e,node*2+1,index,dif);
	tree[node] = tree[node*2] + tree[node*2+1];
	return;
}

int find(int s, int e, int node, int l, int r) { //구간 찾기
	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 %d",&n,&m);
	//동적할당
	int *start = (int*) malloc(sizeof(int)*(n+1));
	int *end = (int*) malloc(sizeof(int)*(n+1));
	list *vec = (list*) malloc(sizeof(list)*(n+1));
	
	for(int i=1;i<=n;i++) { //입력받기
		scanf("%d",&tmp);
		if(tmp!=-1) insert(tmp, i, vec);
	}
	
	dfs(1,start,end,vec); //ETT
	
	while(m--) { //query
		int a,b,c;
		scanf("%d %d",&a,&b);
		if(a==1) { //update
			scanf("%d",&c);
			update(1,n,1,start[b],c);
		} else { //find
			printf("%d\n",find(1,n,1,start[b],end[b]));
		}
	}
}

 

풀이 : 세그먼트 트리, 오일러 경로 트릭

회사 문화 2는 위에서 아래로 전체적으로 영향을 받는 문제였다면

회사 문화 3은 반대로 아래서 위로 영향을 받는 문제입니다.

 

회사 문화 2의 경우 update는 수정하고자 하는 사람의 ETT을 통해서 구한 시작번호, 종료번호를 이용해 구간 수정을 하고

find은 특정 사람의 값을 찾기 위해 단일 찾기를 했다면

 

반대로 회사 문화 3의 경우 update는 수정하고자 하는 사람의 시작번호를 가지고 단일 수정 (ETT로 얻은)

find은 찾고자 하는 사람의 시작번호, 종료번호를 이용한 구간 찾기를 하면 됩니다!!!!

 

위에서 아래로 수정
구간 수정, 단일 찾기

아래에서 위로 수정
단일 수정, 구간 찾기

 

단일 수정이나 탐색을 할 때 ETT 을 통해 얻은 시작번호로만 하는 이유는, 시작번호는 모든 그래프의 노드에 서로다른 값을 가지나, 종료번호는 다른 그래프 노드들이 중복된 값을 가지고 있을 수 (100% 중복이 발생합니다) 있기 때문입니다.