[USACO17JAN]Promotion Counting P

题目描述

The cows have once again tried to form a startup company, failing to remember from past experience that cows make terrible managers!

The cows, conveniently numbered \(1 \ldots N\) (\(1 \leq N \leq 100,000\)), organize the company as a tree, with cow 1 as the president (the root of the tree). Each cow except the president has a single manager (its "parent" in the tree). Each cow \(i\) has a distinct proficiency rating, \(p(i)\), which describes how good she is at her job. If cow \(i\) is an ancestor (e.g., a manager of a manager of a manager) of cow \(j\), then we say \(j\) is a subordinate of \(i\).

Unfortunately, the cows find that it is often the case that a manager has less proficiency than several of her subordinates, in which case the manager should consider promoting some of her subordinates. Your task is to help the cows figure out when this is happening. For each cow \(i\) in the company, please count the number of subordinates \(j\) where \(p(j) > p(i)\).

奶牛们又一次试图创建一家创业公司，还是没有从过去的经验中吸取教训--牛是可怕的管理者！

为了方便，把奶牛从 \(1\sim n\) 编号，把公司组织成一棵树，1 号奶牛作为总裁（这棵树的根节点）。除了总裁以外的每头奶牛都有一个单独的上司（它在树上的 “双亲结点”）。

所有的第 \(i\) 头牛都有一个不同的能力指数 \(p_i\)，描述了她对其工作的擅长程度。如果奶牛 \(i\) 是奶牛 \(j\) 的祖先节点，那么我们我们把奶牛 \(j\) 叫做 \(i\) 的下属。

不幸地是，奶牛们发现经常发生一个上司比她的一些下属能力低的情况，在这种情况下，上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之，对于公司的中的每一头奶牛 \(i\)，请计算其下属 \(j\) 的数量满足 \(p_j > p_i\)。

输入格式

The first line of input contains \(N\).

The next \(N\) lines of input contain the proficiency ratings \(p(1) \ldots p(N)\) for the cows. Each is a distinct integer in the range \(1 \ldots 1,000,000,000\).

The next \(N-1\) lines describe the manager (parent) for cows \(2 \ldots N\). Recall that cow 1 has no manager, being the president.

输入的第一行包括一个整数 \(n\)。

接下来的 \(n\) 行包括奶牛们的能力指数 \(p_1,p_2 \dots p_n\)。保证所有数互不相同。

接下来的 \(n-1\) 行描述了奶牛 \(2 \sim n\) 的上司的编号。再次提醒，1 号奶牛作为总裁，没有上司。

输出格式

Please print \(N\) lines of output. The \(i\)th line of output should tell the number of subordinates of cow \(i\) with higher proficiency than cow \(i\).

输出包括 \(n\) 行。输出的第 \(i\) 行应当给出有多少奶牛 \(i\) 的下属比奶牛 \(i\) 能力高。

样例 #1

样例输入 #1

样例输出 #1

提示

感谢@rushcheyo 的翻译

【数据范围】
对于 \(100\%\) 的数据，\(1\le n \le 10^5\)，\(1 \le p_i \le 10^9\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define lid (tree[id].lson)
#define rid (tree[id].rson)

using namespace std;

int n, tot;
int a[5211314], b[5211314], len;
int head[5211314], nex[5211314], to[5211314], cnt;
int root[5211314], out[5211314];

struct Segment_Tree {
	int lson, rson;
	int summary;
}tree[52113140];

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch - '0');
		ch = getchar();
	}
	return x * f;
}

inline void AddPoi(int v1, int v2) {
	++ cnt;
	nex[cnt] = head[v1];
	head[v1] = cnt;
	to[cnt] = v2;
	return;
}

class MergeSegmentTree{
	private:
		void PushUp(int id) {
			tree[id].summary = tree[lid].summary + tree[rid].summary;
		}
	public:
		void Update(int &id, int l, int r, int pos, int num) {
			if (id == 0) id = ++ tot;
			if (l == r) {
				tree[id].summary = num;
				return;
			}
			int mid = (l + r) >> 1;
			if (pos <= mid) Update(lid, l, mid, pos, num);
			else Update(rid, mid + 1, r, pos, num);
			PushUp(id);
			return;
		}
		int Merge(int a, int b, int l, int r) {
			if (a == 0) return b;
			if (b == 0) return a;
			if (l == r) {
				tree[a].summary += tree[b].summary;
				return a;
			}
			int mid = (l + r) >> 1;
			tree[a].lson = Merge(tree[a].lson, tree[b].lson, l, mid);
			tree[a].rson = Merge(tree[a].rson, tree[b].rson, mid + 1, r);
			PushUp(a);
			return a;
		}
		int Query(int &id, int l, int r, int vl, int vr) {
			int ans = 0;
			if (id == 0) id = ++ tot;
			if (vl <= l && r <= vr) {
				return tree[id].summary;
			}
			int mid = (l + r) >> 1;
			if (vl <= mid) ans += Query(lid, l, mid, vl, vr);
			if (vr > mid) ans += Query(rid, mid + 1, r, vl, vr);
			return ans;
		}
}ask;

void GetAns(int now) {
	int temp;
	for (int i = head[now]; i != 0; i = nex[i]) {
		GetAns(to[i]);
		root[now] = ask.Merge(root[now], root[to[i]], 1, 100000);
	}
	temp = tree[root[now]].summary;
	temp = temp - ask.Query(root[now], 1, 100000, 1, a[now]);
	out[now] = temp;
	return;
}

int main() {
	n = read();
	for (int i = 1; i <= n; ++ i) {
		a[i] = read();
		b[i] = a[i];
	}
	stable_sort(b + 1, b + 1 + n);
	len = unique(b + 1, b + 1 + n) - (b + 1);
	for (int i = 1; i <= n; ++ i) {
		a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
		ask.Update(root[i], 1, 100000, a[i], 1);
	}
	for (int i = 1, fa; i <= n - 1; ++ i) {
		fa = read();
		AddPoi(fa, i + 1);
	}
	GetAns(1);
	for (int i = 1; i <= n; ++ i) {
		printf("%d\n", out[i]);
	}
	return 0;
}