[BOJ] 3653번 영화 수집

이해하기

 

영화를 한 편 보려면 해당 DVD의 위치를 찾아 뺀다. 그리고 다 본 후에는 맨 위로 가져다 놓는다.

영화 한 편을 볼 때마다 그 DVD의 위에 몇 개의 DVD가 있었는지를 구해야하는 문제이다.

구간 트리를 이용하여 문제를 풀 수 있다.

 

구간 트리를 만드는 아이디어는 DVD의 위치에 0 또는 1을 기록해 놓는 것이다. 이를 바탕으로 누적합을 구하는 구간 트리를 만들어서 현재 위치+1에서 맨 위까지 몇개의 책이 쌓여있는지를 구할 수 있도록 한다.

 

 

전체 코드

 

 

import java.util.Scanner;

public class B3653영화수집 {
	static final int MAX = 200000;
	static int T,N,M;
	static int[] arr;
	static long[] tree;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		T = sc.nextInt();
		for(int tc = 0; tc < T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			arr = new int[N+1];
			tree = new long[MAX*4];
			
			int cnt = 0;
			for(int i = N; i >= 1; i--)
				arr[i] = cnt++;
			
			for(int i = 1; i <= N; i++) {
				update(arr[i],1,1,0,MAX);
			}
			
			for(int m = 0; m < M; m++) {
				int i = sc.nextInt();
				sb.append(query(arr[i]+1,MAX,1,0,MAX)+" ");
				update(arr[i],0,1,0,MAX);
				arr[i] = N++;
				update(arr[i],1,1,0,MAX);
			}
			sb.append("\n");
		}
		System.out.println(sb);
		sc.close();
	}
	
	static long query(int s, int e, int node ,int ns, int ne) {
		if(ne < s || ne > e) return 0;
		if(s <= ns && ne <= e) return tree[node];
		int mid = (ns+ne)/2;
		return query(s,e,node*2,ns,mid)+query(s,e,node*2+1,mid+1,ne);
	}
	
	static long update(int i, int val, int node, int ns, int ne) {
		if(i < ns || ne < i) return tree[node];
		if(ns==ne) return tree[node] = val;
		int mid = (ns+ne)/2;
		return tree[node] = update(i,val,node*2,ns,mid)+update(i,val,node*2+1,mid+1,ne);
	}
}

 

 

구간 트리의 합을 구하거나 업데이트를 할 때 최댓값을 기준으로 수행해야한다. 이를 잘 모르고 그때의 크기 값을 기준으로 했더니 제대로 된 구간 트리가 만들어지지 않는 오류가 생겨 한참을 고민했다.