C++[백준]3006번 터보소트

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

3006번: 터보소트

 

솔루션

---

나는 세그먼트 트리 + 정렬

1) 먼저 배열에 입력을 받으면서 인덱스도 저장을 한다. 

2) 정렬을 한다.

3) 세그먼트 트리 리프노드를 1개로 가정하고 세그먼트 트리를 만든다.

4) 아래의 과정을 반복한다.

4-1)  짝수일 때는 i/2인덱스를 참조하여  해당 인덱스가 어디에 있는지 알 수 있으니, l=0,r =인덱스 로 설정하여  구간의 합을 구해준다.

4-2) 홀수 일 땐  N-i/2를  참조하여 l = 해당 값이 존재했던 인덱스 , r=N-1로 구간을 설정하여 구간의 합을 구할 수 있다.

4-3) 해당 인덱스의 값을 0으로 변경하여준다

 

 

코드

---

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

int seg[400002];
pair<int,int> arr[100002];
int N;

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);
}

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

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);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr, arr + N);
	
	MakeSeg(0, N - 1, 1);

	for (int i = 0; i < N; i++) {
		int l, r;
		int idx;
		if (i & 1) { // 짝수번 시행 될 때
			idx = N - (i + 1) / 2;
			l = arr[idx].second;
			r = N - 1;
		}
		else {//홀수번째 시행 때
			idx = i / 2;
			l = 0;
			r = arr[idx].second;
		}
		cout << getSeg(0, N - 1, l, r, 1)-1 << "\n";
		UpdateSeg(0, N - 1, 1, arr[idx].second);
	}
}