백준3653(영화 수집)

jh Seo·2023년 4월 20일

백준 세그먼트 트리 한번에 못 푼 문제

백준

목록 보기

151/180

개요

백준 3653번: 영화 수집

입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 영화의 수 n과 보려고 하는 영화의 수 m이 주어진다. (1 ≤ n, m ≤ 100,000) 둘째 줄에는 보려고 하는 영화의 번호가 순서대로 주어진다.

영화의 번호는 1부터 n까지 이며, 가장 처음에 영화가 쌓여진 순서는 1부터 증가하는 순서이다. 가장 위에 있는 영화의 번호는 1이다.
출력
각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD를 가장 위에 놓는다.

접근 방식

그냥 배열 스왑으로 하자니 범위가 너무 커서 감이 안 와서 검색해본 결과, 세그먼트 트리로 범위를 두배잡는 형식으로 푸는 방법을 찾았다.
영화 갯수가 N개라면 세그먼트 트리의 리프노드의 갯수를 N*2로 잡고, 영화를 볼때마다 N 다음 인덱스에 차곡차곡 넣는 느낌이다.
N 다음 인덱스에 넣기 위해선 인덱스가 거꾸로 정렬되어있어야한다.
N-1부터 0까지 정렬되어있기 위해서 인덱스 관리용 index배열을 하나 생성해준 후,
```
for (int j = 0; j < n; j++) {
	//책을  쌓을 공간이 인덱스 증가하는 방향으로 생기므로 
	//인덱스값들을 반대로 쌓아야한다.
	index[j] = n-j-1;
```
N-j-1씩 넣어준다.
그 후, 인덱스 0부터 n-1까지 1을 넣고 구간합 세그먼트 트리를 구성한다.

입력값을 받을때 해당 입력값에 해당하는 인덱스 번호를
index배열에서 조회한 후, [해당 인덱스 +1,끝]구간에 해당하는 구간합을
출력한다.

for (int j = 0; j < m; j++) {
	cin >> tmpInput;
	//tmpInput위치에 해당하는 인덱스를 index배열에서 조회한 뒤, 해당 인덱스+1 부터 끝까지의 구간합 출력 
	cout << findHowManyDvdsInTargetRange(index[--tmpInput]+1, firstLeafNodeIdx * 2, 1, 0, firstLeafNodeIdx - 1) << " ";

세그먼트 트리의 해당인덱스에는 -1을 넣고 조상노드들도 -1씩 더하며 갱신해준다.

//해당 노드를 -1로 변경하고 조상노드도 -1씩 빼는식으로 갱신하면서 책을 뺐다는걸 구현
SetAncestorNode(index[tmpInput], -1);

그 후 해당 입력값의 인덱스는 n+j로 변경해준다.
=> 해당 책이맨위에 있다는뜻.
```
//tmpInput의 인덱스는 이제 맨위인 n+j
index[tmpInput] =n+j;
```

n+j인덱스인 리프노드를 1더하고 조상노드들도 갱신하며 책을 맨위에 둔걸 구현

//n+j인덱스의 노드를 1을 더하면서 책을 맨위에 둔것으로 구현
SetAncestorNode(index[tmpInput], 1);

전체 코드

#include<iostream>

using namespace std;

//사이즈는 2^19
int segTree[524'288*2];
//인덱스 값 잡아주는 배열
int index[100'000];
int firstLeafNodeIdx = 524288;


int findHowManyDvdsInTargetRange(int targetL, int targetR, int nodeNum, int curL, int curR) {
	if (targetR < curL || curR < targetL) return 0;
	if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
	int mid = (curL + curR) / 2;
	return findHowManyDvdsInTargetRange(targetL, targetR, nodeNum * 2, curL, mid) +
		findHowManyDvdsInTargetRange(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR);
}

void SetAncestorNode(int idx, int val) {
	int tmpIdx = idx + firstLeafNodeIdx;
	while (tmpIdx > 0) {
		segTree[tmpIdx] += val;
		tmpIdx /= 2;
	}

}

void Input() {
	int testCases=0,n=0,m=0,tmpInput=0;
	cin >> testCases;
	for (int i = 0; i < testCases; i++) {
	fill(segTree, segTree + 524288 * 2, 0);
	fill(index, index + 100'000, 0);
		cin >> n >> m;
		for (int j = 0; j < n; j++) {
			//책을  쌓을 공간이 인덱스 증가하는 방향으로 생기므로 
			//인덱스값들을 반대로 쌓아야한다.
			index[j] = n-j-1;
			SetAncestorNode(j, 1);
		}
		for (int j = 0; j < m; j++) {
			cin >> tmpInput;
			//tmpInput위치에 해당하는 인덱스를 index배열에서 조회한 뒤, 해당 인덱스+1 부터 끝까지의 구간합 출력 
			cout << findHowManyDvdsInTargetRange(index[--tmpInput]+1, firstLeafNodeIdx * 2, 1, 0, firstLeafNodeIdx - 1) << " ";
			//해당 노드를 -1로 변경하고 조상노드도 -1씩 빼는식으로 갱신하면서 책을 뺐다는걸 구현
			SetAncestorNode(index[tmpInput], -1);
			//tmpInput의 인덱스는 이제 맨위인 n+j
			index[tmpInput] =n+j;
			//n+j인덱스의 노드를 1을 더하면서 책을 맨위에 둔것으로 구현
			SetAncestorNode(index[tmpInput], 1);

		}
		cout << '\n';

	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}