[BOJ 14446] Promotion Counting(c++)

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

---

문제 개요

소들로 이루어진 회사가 있고, 조직도가 트리의 형태로 이루어져 있습니다. 각 소들은 업무 숙련도가 있고, 각 소들의 부하 직원들 중 자신보다 능력치가 높은 소들의 수를 세는 문제입니다.

(1 ≤ N ≤ 100,000)

(1 ≤ 숙련도 ≤ 10억)

---

문제 풀이

이 문제는 오일러 경로 테크닉 + 머지 소트 트리를 이용하여 해결할 수 있었습니다.

각 노드를 루트로 한 서브 트리를 세그먼트 트리로 이용할 수 있도록 오일러 경로 테크닉을 이용해 구간으로 변경해주었습니다.

class node {
public:
	int s, e, p;
};

node info[100001];

void dfs(int x) {
	static int i = 0;
	info[i].p = arr[x];
	info[x].s = i++;
	for (int y : edges[x]) {
		dfs(y);
	}
	info[x].e = i - 1;
}

 

이후 머지 소트 트리를 구성한 후 노드 별 자신의 숙련도보다 높은 노드들의 수를 세야하므로 구간 내에서 seg[x].end() - upper_bound()를 통해 간단하게 구할 수 있었습니다. 시간복잡도는 O(N log N)입니다.

---

코드

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

int n;
int arr[100001];
vector<int> seg[100001 * 4];
vector<int> edges[100001];

class node {
public:
	int s, e, p;
};

node info[100001];

void dfs(int x) {
	static int i = 0;
	info[i].p = arr[x];
	info[x].s = i++;
	for (int y : edges[x]) {
		dfs(y);
	}
	info[x].e = i - 1;
}

void init(int x, int s, int e) {
	if (s == e) {
		seg[x].push_back(info[s].p);
		return;
	}
	int mid = s + (e - s) / 2;
	init(x * 2, s, mid);
	init(x * 2 + 1, mid + 1, e);
	seg[x].resize(e - s + 1);
	merge(seg[x * 2].begin(), seg[x * 2].end(), seg[x * 2 + 1].begin(), seg[x * 2 + 1].end(), seg[x].begin());
}

int query(int x, int s, int e, int l, int r, int v) {
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) {
		return seg[x].end() - upper_bound(seg[x].begin(), seg[x].end(), v);
	}
	int mid = s + (e - s) / 2;
	return query(x * 2, s, mid, l, r, v) + query(x * 2 + 1, mid + 1, e, l, r, v);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i < n; i++) {
		int p;
		cin >> p;
		edges[p - 1].push_back(i);
	}
	dfs(0);
	init(1, 0, n - 1);
	for (int i = 0; i < n; i++) {
		int ret = query(1, 0, n - 1, info[i].s, info[i].e, arr[i]);
		cout << ret << '\n';
	}
	return 0;
}