취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15957번 문제인 음악 추천이다.
문제는 아래 링크를 확인하자.

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

주어지는 음악들은 트리구조를 가지고 있으므로, 트리의 각 노드에 dfs순회순 인덱스를 새로 붙여(euler tour technique) 각 노드에 대해 그 노드의 자식들이 자신의 오른쪽에 항상 모여있게 인덱스를 새로 정할 수 있다.

위 새로 정한 인덱스를 이용해 lazy propagation을 지원하는 세그먼트트리를 만들면 시간순에 따라 노래에 점수를 부여하는 시뮬레이션을 빠르게 시행할 수 있다.

각 가수의 목표 점수 달성 시간의 범위를 0 이상 1000000007이하로 잡고, 위의 시뮬레이션을 한번 진행할 때마다 모든 가수의 목표 달성 순간이 들어있을 범위를 각각 절반으로 줄여나가는 이분탐색으로 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int N, K; ll J;

ll lazy[262145];

void upd(int L, int R, int qL, int qR, int qVal, int sI) {
	if (R < qL || qR < L) return;
	if (qL <= L && R <= qR) lazy[sI] += qVal;
	else upd(L, (L + R) / 2, qL, qR, qVal, sI * 2), upd((L + R) / 2 + 1, R, qL, qR, qVal, sI * 2 + 1);
}

ll pointval(int qI) {
	int L = 1, R = 100000, sI = 1;
	while (L < R) {
		if (lazy[sI]) {
			lazy[sI * 2] += lazy[sI];
			lazy[sI * 2 + 1] += lazy[sI];
			lazy[sI] = 0;
		}
		int mid = (L + R) / 2;
		if (qI > mid) L = mid + 1, sI = sI * 2 + 1;
		else R = mid, sI = sI * 2;
	}
	return lazy[sI];
}

vector<int> G[100001];

int idx = 1;
int dfi[100001];
int childcnt[100001];

int dfs(int cur) {
	dfi[cur] = idx++;
	int ret = 0;
	for (auto& node : G[cur]) {
		ret += dfs(node);
	}
	childcnt[cur] = ret++;
	return ret;
}

vector<int> singer[100000]; // [i]: i번 가수가 부른 곡들의 num

struct query {
	int idx; // singernum
	int low = 0, mid = 500000003, high = 1000000007;
};

bool qcomp(query& q1, query& q2) {
	return q1.mid < q2.mid;
}

query queries[100000];

struct datum {
	int T;
	int qL, qR, qVal;
	datum() {};
	datum(int T, int qL, int qR, int qVal) {
		this->T = T, this->qL = qL, this->qR = qR, this->qVal = qVal;
	}
};

bool dcomp(datum& d1, datum& d2) {
	return d1.T < d2.T;
}

datum DATA[100000];

void PBS() {
	for (auto& x : lazy) x = 0;
	sort(queries, queries + N, qcomp);

	int kI = 0, qI = 0;
	while (kI < K && qI < N) {
		if (DATA[kI].T > queries[qI].mid) {
			if (queries[qI].high == queries[qI].low) {
				qI++;
				continue;
			}
			ll total = 0;
			for (auto x: singer[queries[qI].idx]) {
				total = min(total + pointval(dfi[x]), 1000000000000000007LL);
			}

			if (total > J * singer[queries[qI].idx].size()) queries[qI].high = queries[qI].mid;
			else queries[qI].low = queries[qI].mid + 1;

			queries[qI].mid = (queries[qI].high + queries[qI].low) / 2;

			qI++;
		}
		else {
			upd(1, 100000, DATA[kI].qL, DATA[kI].qR, DATA[kI].qVal, 1);
			kI++;
		}
	}
	while (qI < N) {
		if (queries[qI].high == queries[qI].low) {
			qI++;
			continue;
		}
		ll total = 0;
		for (auto x : singer[queries[qI].idx]) {
			x = dfi[x];
			total = min(total + pointval(x), 1000000000000000007LL);
		}

		if (total > J * singer[queries[qI].idx].size()) queries[qI].high = queries[qI].mid;
		else queries[qI].low = queries[qI].mid + 1;

		queries[qI].mid = (queries[qI].high + queries[qI].low) / 2;

		qI++;
	}
}

int ans[100001];

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

	cin >> N >> K >> J;
	for (int i = 2; i <= N; i++) {
		int x; cin >> x;
		G[x].emplace_back(i);
	}

	dfs(1);

	for (int i = 1; i <= N; i++) {
		int x; cin >> x; x--;
		singer[x].emplace_back(i);
	}

	for (int i = 0; i < N; i++) queries[i].idx = i;

	for (int k = 0; k < K; k++) {
		int T, P, S; cin >> T >> P >> S;
		DATA[k] = datum(T, dfi[P], dfi[P] + childcnt[P], S / (childcnt[P] + 1));
	}

	sort(DATA, DATA + K, dcomp);

	for (int i = 0; i < 31; i++) {
		PBS();
	}

	for (int i = 0; i < N; i++) {
		query& q = queries[i];
		for (auto& song : singer[q.idx]) {
			ans[song] = q.low;
		}
	}

	for (int i = 1; i <= N; i++) {
		if (ans[i] == 1000000007) cout << -1 << '\n';
		else cout << ans[i] << '\n';
	}
}