[C++][백준] 달리기(2517) - 세그먼트트리

문제

KOI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다.

각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다. 예를 들어, 4번째로 달리고 있는 평소 실력이 7인 선수는 그 앞에서 달리고 있는 선수들 중 평소 실력이 2인 선수만 앞지르는 것이 가능하고 평소실력이 8과 10인 선수들은 앞지르는 것이 불가능하므로, 최선의 등수는 3등이 된다.

선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다.  

 

출력

각 선수의 최선의 등수를 나타내는 정수 N개를 입력에 주어진 선수 순서와 동일한 순서로 한 줄에 하나씩 출력한다.

 

풀이

최선 등수는 현재 등수 - (나보다 등수가 앞서면서 실력이 떨어지는 선수 수의 합)입니다.

 

 

예를 들어 6번 idx의 선수를 살펴봅시다.

6번 선수의 최선 등수는 2등입니다.

이는 현재 등수(6) - (나보다 앞서면서 실력이 떨어지는 선수 수의 합(4))입니다.

 

세그먼트트리를 활용하여 문제를 풀수 있습니다.

 

세그먼트트리의 리프노드의 경우

idx 실력 선수 수 정보를 담고있습니다

 

리프노드가 아닌 경우 

l~r 실력 사이에 있는 선수 수 정보를 담고있습니다. 

 

예를들어 6번 idx 선수의 최선 등수를 구해보도록 하겠습니다.

현재 세그먼트 트리 상태는 다음과 같습니다.

실력이 1~15 사이의 선수 수는 5명입니다. 

6번 선수의 최선 등수를 구하기 위해서는 6번 선수의 실력(9)보다 약한 선수의 수를 구해야 합니다.

 

 

6번 선수의 실력(9)보다 약한 선수의 수는 2번 node의 값인 4입니다.

따라서 6번 선수의 최선 등수를 현재 등수 - (나보다 등수가 앞서면서 실력이 떨어지는 선수 수의 합)으로 구해주고 

6번 선수의 실력을 세그먼트 트리에 insert 해줍니다.

 

해당 문제에서 한가지 문제점이 있는데요, 실력을 index로 세그먼트 트리를 만들어주어야 하는데

실력의 범위가 1,000,000,000입니다. 값이 너무 커서 세그먼트 트리를 배열로 만들어 줄 수 없습니다.

그러나 선수의 수는 500,000명 이하라는 것에서 해결할 수 있습니다.

실력을 상대 실력으로 변환해주면 가장 큰 실력의 값은 500,000 일것입니다.

 

 

struct myData {
	int ability;
	int idx;
};

// 능력순으로 오름차순
bool comp1(const myData& data1, const myData& data2) {
    return data1.ability < data2.ability;
}

int abilityVal = 1;
for (int i = 0; i < N; i++) {
    input[i].ability = abilityVal++;
}

// indx순으로 오름차순
bool comp2(const myData& data1, const myData& data2) {
	return data1.idx < data2.idx;
}

따라서 실력과 index를 담는 구조체를 생성하고

능력순으로 오름차순 정렬하여 실력을 상대 실력으로 변환해줍니다.

그리고 기존 index 순서로 복귀해야 하기 때문에 다시 index 오름차순으로 정렬해줍니다.

 

전체 코드는 아래와 같습니다.

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

int N;
const int MAX = 500010;
int tree[MAX * 4];

struct myData {
	int ability;
	int idx;
};

vector<myData> input;

int update(int index, int node, int l, int r) {
	if (index < l || index > r) {
		return tree[node];
	}
	else if (l == r) {
		tree[node]++;
		return tree[node];
	}
	int mid = (l + r) / 2;
	return tree[node] = update(index, node * 2, l, mid) + update(index, node * 2 + 1, mid + 1, r);
}

int sum(int start, int end, int node, int l, int r) {
	if (start > r || end < l) {
		return 0;
	}
	if (start <= l && end >= r) { //r<=MAX
		return tree[node];
	}
	int mid = (l + r) / 2;
	return sum(start, end, node * 2, l, mid) + sum(start, end, node * 2 + 1, mid + 1, r);
}

// 능력순으로 오름차순
bool comp1(const myData& data1, const myData& data2) {
	return data1.ability < data2.ability;
}

bool comp2(const myData& data1, const myData& data2) {
	return data1.idx < data2.idx;
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) { // 2
		int strength; // 8
		cin >> strength;

		input.push_back({ strength, i });
	}

	sort(input.begin(), input.end(), comp1);

	int abilityVal = 1;
	for (int i = 0; i < N; i++) {
		input[i].ability = abilityVal++;
	}

	sort(input.begin(), input.end(), comp2);

	for(int i = 1; i<= N; i++) {
		int value = sum(1, input[i - 1].ability - 1, 1, 1, MAX);
		printf("%d\n", i - value);
		update(input[i - 1].ability, 1, 1, MAX);
	}

	return 0;
}