[P4] 백준 3653번 영화 수집 C++ 세그먼트 트리

리뷰

 

업데이트를 통해 세그먼트 트리를 확장하고 구간합을 구하는 문제

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

 

전역 변수

• tc, n, m : 테스트 케이스의 개수 tc, 각 테케의 DVD의 수 n, 각 테케의 쿼리의 수 m
• lst : DVD의 초기정보와 인덱스 정부를 담은 정수형 벡터
• tree : 세그먼트 트리의 구간합 정보를 담은 정수형 벡터

 

함수

1. update

void update(int node, int s, int e, int idx, int val)

 

1. 세그먼트 트리의 특정 인덱스의 값을 교체하고 구간합을 업데이트 하는 함수
2. val은 1과 -1이 올 것이며 음수가 올 경우는 주어지지 않는다.

 

2. query

int query(int node, int s, int e, int L, int R)

 

1. 구간의 합을 계산할 함수
2. 1과 0으로만 이루어져 있으므로 int형 타입으로도 충분히 나타낼 수 있다.

 

3. init

void init()

 

1. 각 테스트 케이스 마다 벡터를 clear해줄 함수

 

4. input

void input()

 

1. n과 m을 입력받고 lst와 tree벡터를 초기화 해줄 함수

 

5. solution

void solution()

 

1. 입력된 쿼리에 따라 구간합과 업데이트를 진행할 함수
2. 새로운 인덱스 new_index를 세그먼트 트리의 끝인 n + 1로 초기화 해준다.
3. 입력받은 수의 인덱스를 찾아 해당 인덱스 + 1 ~ n + m까지의 구간합을 구해준 뒤 출력해 준다.
4. 해당 인덱스의 세그먼트 트리 노드에 -1처리를 해주어 0으로 만들어 준 뒤 구간합을 업데이트 해준다.
5. 세그먼트 트리 new_index 노드에 1을 더해주고 구간합을 업데이트 해준다.
6. 현재 숫자의 인덱스 값을 new_index로 새로 할당해 주고 new_index의 값을 1만큼 증가시켜 준다.

 

문제풀이

1. tc를 입력 받고 tc만큼의 테스트 케이스를 개행해 준다.
2. init 함수를 통해 이전 테스트 케이스에 사용한 lst와 tree벡터를 초기화 해준다.
3. input 함수를 통해 n, m값을 받아주고 lst를 n + 1크기로, tree를 (n + m) * 4크기로 초기화 해준다. (값은 0)
4. lst벡터의 인덱스에 역순으로 값을 입력받아 저장해 준다.
5. update함수를 통해 lst벡터의 i번째 인덱스의 트리 노드에 1을 더해준다.
6. solution함수를 통해 DVD를 꺼내고 맨 위에 올려놓는 작업을 반복해 준다.
7. 각 쿼리마다 현재 DVD위에 존재하는 DVD의 갯수를 출력해 주고, 쿼리가 끝나면 줄바꿈을 실행해 준다.
8. 테스트 케이스마다 위 작업을 반복해 준다.

 

참고 사항

1. 1-based-indexing을 사용했으므로 0번 인덱스는 사용하지 않았다.
2. 최악의 케이스일 경우 n + m번째 인덱스까지 처리가 필요하므로 업데이트와 쿼리는 1 ~ n + m까지 탐색을 진행한다.
3. 위 사유로 인해 세그먼트 트리의 크기는 (n + m) * 4개가 있어야 인덱스 에러를 맞지 않는다.

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;

int tc, n, m;
vector<int> lst, tree;

void update(int node, int s, int e, int idx, int val) {
	if (s == idx && e == idx) {
		tree[node] += val;
		return;
	}
	int mid = (s + e) / 2;
	if (s <= idx && idx <= mid) update(node * 2, s, mid, idx, val);
	else update(node * 2 + 1, mid + 1, e, idx, val);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	int left = query(node * 2, s, mid, L, R);
	int right = query(node * 2 + 1, mid + 1, e, L, R);
	return left + right;
}

void init() {
	lst.clear();
	tree.clear();
}

void input() {
	cin >> n >> m;
	lst.resize(n + 1);
	tree.resize((n + m) * 4, 0);
	for (int i = 1; i <= n; i++) {
		lst[i] = n - i + 1;
		update(1, 1, n + m, lst[i], 1);
	}
}

void solution() {
	int new_index = n + 1;
	for (int i = 1; i <= m; i++) {
		int a; cin >> a;
		int idx = lst[a];
		cout << query(1, 1, n + m, idx + 1, n + m) << " ";
		update(1, 1, n + m, idx, -1);
		update(1, 1, n + m, new_index, 1);
		lst[a] = new_index++;
	}
	cout << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> tc;
	while (tc--) {
		init();
		input();
		solution();
	}
}