c언어 3653번 영화 수집 (백준)

#include <stdio.h>

int tree[200001]; //tree 배열
int arr[100001]; //요소의 위치를 담을 배열

int sum(int x) { //Fenwick Tree 누적합 구하기
	int ans = 0;
	while(x) {
		ans += tree[x];
		x -= x&(-x);
	}
	return ans;
}

void update(int x, int n, int dif) { //Fenwick Tree 수정하기
	while(x<=n) {
		tree[x] += dif;
		x += x&(-x);
	}
}

int main(void) {
	int t; //테스트 케이스
	scanf("%d", &t);
	
	while(t--) {
		int n, m, nm; //nm = n+m을 저장할 변수
		scanf("%d %d", &n, &m);
		nm = n+m;
        for(int i=0; i<=n; i++) arr[i] = tree[i] = 0; //배열 초기화
        for(int i=n; i<=nm; i++) tree[i] = 0;
		
		for(int i=m+1; i<=nm; i++) { //m+1~n+m까지 전부 1로 업데이트 한다.
			update(i, nm, 1);
			arr[i-m] = i;
		}
		
		int insert = m; //DVD를 꺼내서 위에다가 넣을때의 위치
		
		for(int i=0; i<m; i++) { //m번 반복
			int k; //알아볼 DVD의 번호
			scanf("%d", &k);
			printf("%d ", sum(arr[k]-1)); //k번째의 DVD위에 몇개의 DVD가 있는가?
			update(arr[k], nm, -1); //꺼냈기 때문에, 더 이상 이 위치에 DVD가 없으니 1->0으로 update
			arr[k] = insert--; //k번째의 DVD는 insert위치에 존재하게 된다. 그 다음 insert의 위치를 1 감소시킨다.
			update(arr[k], nm, +1); //insert위치에 DVD가 생겼으니 0->1로  update
		}
		printf("\n");
	}
}

 

풀이 : 단일 수정, 범위 질문으로 볼 수 있기에, 여기서도 Fenwick Tree을 사용할 수 있다.

 

 

tree배열은 tree을 위한 공간임에 동시에, DVD가 들어갈 수 있는 공간 전체를 의미한다.

DVD가 들어가 있는 공간을 1, 없는 공간을 0으로 두며, 나중에 구간합을 사용하여, 특정구간의 DVD가 몇개 있는지를 구하게 한다.

 

 

arr배열에는 현재 특정 번호의 DVD의 위치를 담고 있다.

 

만약 위에서 DVD 3번을 꺼낼려고 하면,

세그먼트 트리의 부분합을 구하는 방식을 이용하여, 3이전까지 범위에 DVD가 몇개있는지에 대한 구간합을 구할 수 있다.

 

그런다음 DVD 3번의 위치를 바꾸어 주면 된다.

먼저 기존의 DVD3번와 관련된 tree의 값들에 -1해주며

위치를 저장하는 3번에 해당하는 arr배열의 값을 바꾼다음

마지막으로 새로운 공간과 관련된 tree의 값들에 +1을 해준다.

 

 

 

 

 

 

 

 

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

3653번: 영화 수집