C++[백준]3653번 영화 수집

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

3653번: 영화 수집

 

솔루션

---

세그먼트 트리를 공부하며 문제를 풀고 있다.

 

나는 이 문제를 세그먼트 트리를 이용해 해결하였다.

 

1) N이 들어오면, 책의 번호를  1 = N, 2=N-1, ... N = 1 이렇게 저장 할 배열을 하나 선언하고, 배열에 값을 채운다.

 

2) 그리고 세그먼트 트리를 만든다. 각각의 리프노드의 값은 1로 하고, 총 개수를 세는 세그먼트 트리를 만든다.

 

3) M을 입력 받을 때 다음의 과정을 걸친다. (for int i=0;i<M;i++)

3-1) 입력으로 들어온 배열의 인덱스를 찾는다. (1의 과정에서 수행 한 것)

3-2) 해당 배열의 값+1, 200,000까지의 개수의 합을 출력한다. (2에서 만든 세그먼트 트리)

3-3) 해당 배열이 원래 위치했던 곳은 -1줄여주고, 다음에 위치할 인덱스를 N+i로 수정하며 세그먼트 트리를 갱신한다.

 

 

3-2에서 200000를 끝점으로 잡았는지에 대한 설명 :

 N은 100,000까지 들어오는데 나는 1)의 과정을 통해 배열에 인덱스로 저장 해 놓기 떄문에, M번 쿼리가 들어오면 최대 가능한 인덱스는 N+M즉 200,000이다. 따라서 세그먼트 트리 크기도 (N+M)*2로 선언한다.

 

 

코드

---

#define MAX 200000
#include <iostream>
#include <cstring>
using namespace std;

int idx, N, M;
int arr[100001];
int seg[600002];

int makeSeg(int str, int end, int node) {
	if (str == end) return seg[node] = 1;
	int mid = (str + end) / 2;
	return seg[node] = makeSeg(str, mid, node * 2) + makeSeg(mid + 1, end, node * 2 + 1);
}

void UpdateSeg(int str, int end, int node, int idx, int value) {
	seg[node] += value;
	if (str == end) return;
	int mid = (str + end) / 2;
	if (idx <= mid) return UpdateSeg(str, mid, node * 2, idx, value);
	else return UpdateSeg(mid + 1, end, node * 2 + 1, idx, value);
}

int getSeg(int str, int end, int l, int r, int node) {
	if (str > r || end < l) return 0;
	if (str >= l && end <= r) return seg[node];
	int mid = (str + end) / 2;
	return getSeg(str, mid, l, r, node * 2) + getSeg(mid + 1, end, l, r, node * 2 + 1);
}

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

	while(tc--){
		cin >> N >> M;
		
		idx = N - 1;
		for (int i = 0; i < N; i++) {
			arr[i] = idx;
			UpdateSeg(0, MAX, 1, idx--, 1);
		}
		
		idx = N;
		for (int i = 0; i < M; i++) {
			int value;
			cin >> value;
			value--;
			int left = arr[value];
			cout << getSeg(0, MAX, left+1, MAX, 1) << " ";
			UpdateSeg(0, MAX, 1, left, -1);
			arr[value] = idx;
			UpdateSeg(0, MAX, 1, idx++, 1);
		}
		memset(seg, 0, sizeof(seg));
		cout << "\n";
	}
}