[BOJ 8308] Firm(c++)

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

---

문제 개요

회사에 새로운 직원이 입사하거나, 특정 직원의 k차 부하 직원 수를 조회하는 쿼리를 처리하는 문제입니다. degree가 0은 직속 부하, 1은 부하의 부하, k는 k 단계 밑의 부하입니다.

• Z p s : 직원 p가 입사하며, 직속 상사는 s
• P q k: 직원 q가 degree k 상사인 부하 직원의 수(즉, q로부터 k 단계 아래에 있는 직원 수)

(1 ≤ N, q, k ≤ 10⁵)

(2 ≤ q, k ≤ 10⁵)

---

문제 풀이

이 문제는 오프라인 쿼리 + 오일러 투어 테크닉 + 동적 머지소트 트리를 통해 문제를 해결하였습니다.

 

트리가 동적으로 업데이트 되기 때문에 모든 쿼리를 먼저 읽고 트리 구조를 완성한 후 처리를 하였습니다.

int main(){
	for (int i = 0; i < n; i++) {
		char ch;
		int x, y;
		cin >> ch >> x >> y;
		if (ch == 'Z') {
			edge[y].push_back(x);
			s++;
		}
		queries.push_back({ ch, x, y });
	}
	for (Q cur : queries) {
		// 오프라인 쿼리
	}
}

 

완성된 트리를 기반으로 오일러 경로 테크닉으로 각 노드를 DFS로 방문하며 구간을 할당하였습니다.

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

node info[100001];

void dfs(int x, int d) {
    static int i = 0;
    info[x].degree = d;        // 해당 노드의 깊이
    info[x].s = i++;           // 시작 지점
    for (int y : edge[x]) {
        dfs(y, d + 1);
    }
    info[x].e = i - 1;         // 종료 지점
}

이를 통해 노드 x의 서브트리에 속한 모든 노드는 [info[x].s, info[x].e] 구간에 위치합니다.

 

머지소트 트리를 동적으로 노드가 추가되기 때문에 매번 전체를 정렬하는 대신 정렬해야할 부분만 정렬을 하는 것이 핵심이었습니다. 정렬된 사이즈를 갱신하며 새로 추가된 부분만 정렬하여 병합하여 처리하였습니다.

int last_sorted_size[100001 * 4];


void ensure_sorted(int x) {
	if (last_sorted_size[x] < seg[x].size()) {
		sort(seg[x].begin() + last_sorted_size[x], seg[x].end()); // 새로운 부분만 정렬
		inplace_merge(seg[x].begin(),
			seg[x].begin() + last_sorted_size[x],
			seg[x].end()); // 정렬된 두 부분을 병합
		last_sorted_size[x] = seg[x].size();
	}
}

이렇게 하면 각 세그먼트 노드당 한 번씩만 정렬한 것과 같은 효과를 냅니다.

시간복잡도는 O(N log N + Q log² N)입니다.

---

코드

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

int n, s;

class Q {
public:
	char c;
	int x, y;
};

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

vector<Q> queries;
vector<int> edge[100001];
node info[100001];

int last_sorted_size[100001 * 4];

vector<int> seg[100001 * 4];

void dfs(int x, int d) {
	static int i = 0;
	info[x].degree = d;
	info[x].s = i++;
	for (int y : edge[x]) {
		dfs(y, d + 1);
	}
	info[x].e = i - 1;
}

void update(int x, int s, int e, int idx) {
	if (info[idx].s < s || e < info[idx].s) return;
	seg[x].push_back(info[idx].degree);	
	if (s == e) {		
		return;
	}
	int mid = s + (e - s) / 2;
	update(x * 2, s, mid, idx);
	update(x * 2 + 1, mid + 1, e, idx);
}

void ensure_sorted(int x) {
	if (last_sorted_size[x] < seg[x].size()) {
		sort(seg[x].begin() + last_sorted_size[x], seg[x].end());
		inplace_merge(seg[x].begin(),
			seg[x].begin() + last_sorted_size[x],
			seg[x].end());
		last_sorted_size[x] = seg[x].size();
	}
}

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) {
		ensure_sorted(x);
		return upper_bound(seg[x].begin(), seg[x].end(), v)
			- lower_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++) {
		char ch;
		int x, y;
		cin >> ch >> x >> y;
		if (ch == 'Z') {
			edge[y].push_back(x);
			s++;
		}
		queries.push_back({ ch, x, y });
	}
	dfs(1, 1);
	update(1, 0, s, 1);
	for (Q cur : queries) {
		if (cur.c == 'Z') {
			update(1, 0, s, cur.x);
		}
		else {
			int ret = query(1, 0, s, info[cur.x].s, info[cur.x].e, cur.y + info[cur.x].degree + 1);
			cout << ret << '\n';
		}
	}
	return 0;
}