RT

P3605 [USACO17JAN]Promotion Counting P

# include <iostream>
# include <cstdio>
# include <algorithm>

using namespace std;
const int N = 1e5 + 5;
typedef struct {
	int ls , rs , Kikyo_;
}Tr;
Tr tr[N * 4];
typedef struct {
	int x , y , next;
}Edge;
Edge edge[N * 4];
int E = 0 , elast[N];
void add(int x , int y) {
	E ++;
	edge[E].x = x;
	edge[E].y = y;
	edge[E].next = elast[x];
	elast[x] = E;
}
int n;
int a[N] , val[N];
int root[N];
int tot = 0;
void build(int &Root , int l , int r , int val) {
	Root = ++ tot;
	tr[Root].Kikyo_ = 1;
	if (l == r) return ;
	int mid = (l + r) >> 1;
	if (val <= mid) build(tr[Root].ls , l , mid , val);
	else build(tr[Root].rs , mid + 1 , r , val);
	
}
void merge(int &x , int y) {
	if (!x || !y) {
		x += y;
		return ;
	}
	tr[x].Kikyo_ += tr[y].Kikyo_;
	merge(tr[x].ls , tr[y].ls);
	merge(tr[x].rs , tr[y].rs);

}
int ans[N];

int query(int Root , int l , int r , int x , int y) {
	if (x <= l && r <= y) return tr[Root].Kikyo_;
	int ans = 0 , mid = (l + r) >> 1;
	if (x <= mid) ans += query(tr[Root].ls , l , mid , x , y);
	if (y > mid) ans += query(tr[Root].rs , mid + 1 , r , x , y);
	return ans;
}
int m;
void dfs(int x) {
	for (int i = elast[x] ; i ; i = edge[i].next) {
		int y = edge[i].y;
		dfs(y);
		merge(root[x] , root[y]);
	}
	ans[x] = query(root[x] , 1 , n , val[x] + 1 , n);
}


int x;
int main() {
	cin >> n;
	for (int i = 1 ; i <= n ; i ++) {
		scanf("%d" , &a[i]);
		val[i] = a[i];
	}
	for (int i = 2 ; i <= n ; i ++) {
		scanf("%d" , &x);
		add(x , i);
	}
	sort(a + 1 , a + 1 + n);
	for (int i = 1 ; i <= n ; i ++) {
		val[i] = lower_bound(a + 1 , a + 1 + n, val[i]) - a;
		build(root[i] , 1 , n , val[i]);
	}
	dfs(1);
	for (int i = 1 ; i<= n ; i ++) {
		printf("%d\n" , &ans[i]);
	}
	return 0;
}