[백준/BOJ] 백준 3653번 : 영화 수집

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

3653번: 영화 수집

dvd 벡터에 처음 m 개는 꺼내고 다시 올려놓을 곳으로 비워놓고(0을 넣어 놓고) 그다음 n개의 영화를 놓는 것으로(1을 넣어 놓는다) dvd의 초기 상태를 나타낸다. [영화 번호] = dvd 벡터의 어느 인덱스에 있는지를 나타내는 movie_index를 통해 어떤 영화가 dvd 벡터의 어떤 인덱스에 있는지 나타내고, dvd 벡터의 상태를 세그먼트 트리로 나타낸다. 그리고 영화 번호를 입력받으면 0 ~ movie_index[영화 번호] - 1의 합을 세그먼트 트리 쿼리를 이용해 구한다 해당 값이 그 영화를 볼 때 그 영화 위에 있었던 영화들의 개수가 된다. 그리고 세그먼트 트리의 movie_index[movie_number]위치(뽑은 영화의 위치)를 0으로 업데이트하고, m - 1 - i위치(뽑은 영화가 다시 들어갈 위치)를 1로 업데이트한다. 그리고 movie_index의 movie_number영화의 새로운 위치로 업데이트한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int tc;
int n, m;
vector<int> sgmtt;
vector<int> dvd;
vector<int> movie_index; //[영화 번호] = dvd의 어느 인덱스에 있는지
vector<int> result;

//세그먼트 트리 만들기
int Make_sgmtt(int here, int index_left, int index_right)
{
	if (index_left == index_right)
		return sgmtt[here] = dvd[index_left];

	int mid = (index_left + index_right) / 2;

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return sgmtt[here] = Make_sgmtt(left_child, index_left, mid) + Make_sgmtt(right_child, mid + 1, index_right);
}

int Update_sgmtt(int here, int index_left, int index_right, int update_index, int update_val)
{
	//업데이트 하는 인덱스일때
	if (index_left == index_right && index_left == update_index)
		return sgmtt[here] = update_val;

	//업데이트 하는 인덱스와 상관 없는곳일때
	if (update_index < index_left || index_right < update_index)
		return sgmtt[here];

	int mid = (index_left + index_right) / 2;

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return sgmtt[here] = Update_sgmtt(left_child, index_left, mid, update_index, update_val) + Update_sgmtt(right_child, mid + 1, index_right, update_index, update_val);
}

int Query_sgmtt(int here, int index_left, int index_right, int find_index_left, int find_index_right)
{
	//구하려는 구간과 상관 없을때
	if (find_index_right < index_left || index_right < find_index_left)
		return 0;

	//현재 구간이 구하려는 구간안에 속할때
	if (find_index_left <= index_left && index_right <= find_index_right)
		return sgmtt[here];

	int mid = (index_left + index_right) / 2;

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return Query_sgmtt(left_child, index_left, mid, find_index_left, find_index_right) + Query_sgmtt(right_child, mid + 1, index_right, find_index_left, find_index_right);
}

void Pre()
{
	result.clear();

	dvd.clear();

	//처음 m개는 꺼내고 다시 올려놓을 곳으로 비어놓는다
	for (int i = 0; i < m; i++)
		dvd.push_back(0);

	//n개의 dvd가 놓여있다
	for (int i = 0; i < n; i++)
		dvd.push_back(1);

	sgmtt.clear();
	sgmtt.resize((n + m) * 4); //세그먼트 트리의 크기를 넉넉하게 (n + m) * 4 로 한다
	Make_sgmtt(0, 0, n + m - 1);

	movie_index.clear();
	movie_index.resize(n + 1);
	for (int i = 1; i <= n; i++)
	{
		movie_index[i] = m - 1 + i; //초기에 i번호의 영화는 dvd의 m - 1 + i 인덱스에 있다
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		cin >> n >> m;

		Pre();

		for (int i = 0; i < m; i++)
		{
			int movie_number;
			cin >> movie_number;

			//0 ~ movie_index[movie_number] - 1 의 합을 세그먼트 트리 쿼리를 이용해 구한다
			int query_result = Query_sgmtt(0, 0, n + m - 1, 0, movie_index[movie_number] - 1);
			result.push_back(query_result);

			//movie_index[movie_number]위치(뽑은 영화의 위치)를 0으로 업데이트 한다
			Update_sgmtt(0, 0, n + m - 1, movie_index[movie_number], 0);

			//m - 1 - i위치(뽑은 영화가 다시 들어갈 위치)를 1로 업데이트 한다
			Update_sgmtt(0, 0, n + m - 1, m - 1 - i, 1);

			//movie_number영화의 새로운 위치를 업데이트 한다
			movie_index[movie_number] = m - 1 - i;
		}

		for (int i = 0; i < result.size(); i++)
			cout << result[i] << " ";
		cout << "\n";
	}

	return 0;
}