[P5] 백준 4297번 Ultra-QuickSort C++ 세그먼트 트리, 값/좌표 압축, 정렬

리뷰

 

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

간단한 세그먼트 트리 문제

 

 

전역 변수

• N : N의 상한값을 정의하기 위한 상수 변수
• n : 원소의 개수를 저장할 변수
• a : 원본 배열 정보를 저장할 벡터
• c : 값/압축된 배열 정보를 저장할 벡터
• tree : 세그먼트 트리 정보를 저장할 벡터

 

함수

1. update

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

 

세그먼트 트리 점 업데이트를 수행하기 위한 함수

 

2. query

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;
	return query(node * 2, s, mid, L, R) + query(node * 2 + 1, mid + 1, e, L, R);
}

 

세그먼트 트리 구간 합 정보를 구하기 위한 함수

 

 

문제풀이

1. a, c를 N으로 reserve, tree를 N*4로 reserve처리한다.
2. n값을 입력 받은 후 n이 0이 아닐 경우를 조건으로 하는 while루프를 수행한다.
3. a, c, tree를 clear처리하여 이전 테스트케이스의 데이터를 제거한다.
4. n개의 원소를 입력 받아 a, c벡터에 각각 추가해준다.
5. sort함수를 통해 c벡터를 오름차순으로 정렬하고, erase+unique를 통해 중복 값을 제거한다.
6. 변수 m을 c의 크기로 저장하고, tree를 m*4크기로 초기화한다.
7. 변수 ans를 0으로 초기화 하고, n개의 원소를 순회한다.
8. 변수 idx에 lower_bound함수를 통해 c벡터를 순회하며 a[i]의 압축된 인덱스를 저장한다.
9. query함수를 통해 idx~m범위의 구간합을 구해 ans에 더해준다,
10. update함수를 통해 idx번째 리프 노드를 증가시키고, 세그먼트 트리 정보를 업데이트한다.
11. 모든 원소를 순회한 후 ans에 저장된 값을 출력하고 개행 문자를 삽입하며 줄바꿈을 수행한다.
12. 매 테스트 케이스마다 위 로직을 반복하여 수행한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 각 원소를 차례대로 순회하며 현재 시점에서 자신보다 큰 원소의 개수만큼 ans에 더해주면 된다.

 

정답 코드

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

const int N = 5e5;
int n;
vector<int> a, c;
vector<int> tree;

void update(int node, int s, int e, int idx) {
	if (s == e) ++tree[node];
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx);
		else update(node * 2 + 1, mid + 1, e, idx);
		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;
	return query(node * 2, s, mid, L, R) + query(node * 2 + 1, mid + 1, e, L, R);
}

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

	a.reserve(N);
	c.reserve(N);
	tree.reserve(N * 4);

	while (cin >> n && n) {
		a.clear();
		c.clear();
		tree.clear();

		for (int i = 0; i < n; ++i) {
			int d; cin >> d;
			a.push_back(d);
			c.push_back(d);
		}

		sort(c.begin(), c.end());
		c.erase(unique(c.begin(), c.end()), c.end());
		int m = c.size();
		tree.resize(m * 4, 0);

		long long ans = 0;
		for (int i = 0; i < n; ++i) {
			int idx = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
			ans += query(1, 0, m - 1, idx, m);
			//cout << a[i] << " " << idx << "\n";
			update(1, 0, m - 1, idx);
		}
		cout << ans << "\n";
	}
}