c언어 2820번 자동차 공장 (백준)

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

int ETT = 0; //오일로 경로 트릭을 위한 변수
int tree[266000]={}, lazy[266000]={}, arr[100001]={}; //lazy propagation

typedef struct list{ //리스트 자료구조를 위한 구조체
    struct list * prev;
    struct list * next;
    int val;
}list;

void insert(int s, int val, list vec[]) { //리스트에 삽입
    list * newNode = (list*) malloc(sizeof(list));
    newNode->val = val;
    newNode->next = vec[s].next;
    newNode->prev = vec+s;
    if(vec[s].next != NULL) vec[s].next->prev = newNode;
    vec[s].next = newNode;
    return;
}

void dfs(int x, int start[], int end[], list vec[]) { //오일러 경로 트릭
    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 lazyU(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) { //수정(갱신)
	lazyU(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 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 %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));
    
    scanf("%d",&arr[1]); //사장의 월급 입력
    for(int i=2; i<=n; i++) { //사원들의 월급, 직속상사 입력
        vec[i].prev = vec[i].next = NULL;
        scanf("%d %d",&arr[i],&tmp);
        insert(tmp, i, vec); //직속상사를 기준으로 vec에 삽입
    }
    
    dfs(1, start, end, vec); //ETT

    for(int i=1; i<=n; i++) { //초기 월급을 갱신해줌
    	update(1,n,1,start[i],start[i],arr[i]);
	}
    
    while(m--) { //query
    	char a;
    	int b,c;
    	scanf(" %c %d",&a,&b);
    	if(a=='p') { //update
    		scanf("%d",&c);
    		update(1,n,1,start[b],end[b],c); //서브 트리의 노드 포함 갱신
    		update(1,n,1,start[b],start[b],-c); //서브 트리의 노드 부분만 다시 빼줌 (결국 서브트리의 노드의 값은 변화가 없다)
		}
    	else { //find
    		printf("%d\n",find(1,n,1,start[b],start[b])); //찾기
		}
	}
	//동적할당 해제
	free(start);
	free(end);
	for(int i=1; i<=n; i++) {
		for(list* p=vec[i].next; p!=NULL; p=p->next) free(p);
	}
	free(vec);
	return 0;
}

 

풀이 : 오일러 경로 트릭, lazy propagation

 

https://h202.tistory.com/756

c언어 14268번 회사 문화 2 (백준)

 

위의 풀이와 거의 동일합니다.

 

단지 쿼리 처리과정에서 update부분이 조금 다를 뿐입니다.

 

주의 : 문제에서 값은 2^31-1 이하라고 했기에 long long int 을 사용하지 않고 int 형으로 처리가 가능합니다.

 

이 코드는 실행시간이 느린 축에 속합니다.