【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化

时间:2023-12-19 13:06:50

题目描述

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 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 (【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化), 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 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化has a distinct proficiency rating, 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化, which describes how good she is at her job. If cow 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 is an ancestor (e.g., a manager of a manager of a manager) of cow 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化, then we say 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 is a subordinate of 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化.

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 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 in the company, please count the number of subordinates 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 where 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化.

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

为了方便,把奶牛从 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 编号,把公司组织成一棵树,1 号奶牛作为总裁(这棵树的根节点)。除了总裁以外的每头奶牛都有一个单独的上司(它在树上的 “双亲结点”)。所有的第 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 头牛都有一个不同的能力指数 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化,描述了她对其工作的擅长程度。如果奶牛 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 是奶牛 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 的祖先节点(例如,上司的上司的上司),那么我们我们把奶牛 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 叫做 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 的下属。

不幸地是,奶牛们发现经常发生一个上司比她的一些下属能力低的情况,在这种情况下,上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之,对于公司的中的每一头奶牛 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化,请计算其下属 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 的数量满足 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化

输入输出格式

输入格式:

The first line of input contains 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化.

The next 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 lines of input contain the proficiency ratings 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 for the cows. Each is a distinct integer in the range 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化.

The next 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 lines describe the manager (parent) for cows 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化. Recall that cow 1 has no manager, being the president.

输入的第一行包括一个整数 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化

接下来的 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 行包括奶牛们的能力指数 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化. 保证所有数互不相同,在区间 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 之间。

接下来的 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 行描述了奶牛 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 的上司(双亲节点)的编号。再次提醒,1 号奶牛作为总裁,没有上司。

输出格式:

Please print 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 lines of output. The 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化th line of output should tell the number of subordinates of cow 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 with higher proficiency than cow 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化.

输出包括 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 行。输出的第 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 行应当给出有多少奶牛 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 的下属比奶牛 【USACO17JAN】Promotion Counting晋升者计数 线段树+离散化 能力高。

输入输出样例

输入样例#1:
5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
输出样例#1:
2
0
1
0
0 题解:
1.先读入每个权值然后离散化编号.
2.然后就是遍历这颗树,然后一边修改一边统计.
3.关键:左子树会影响到右子树的答案,那么我们就在进入右子树之前,先统计一边(答案记为Y),出来之后再统计一遍(答案记为X)那么该点的答案就为X-Y
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int gi(){
int str=;char ch=getchar();
while(ch>''||ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-,ch=getchar();
return str;
}
int val[N],b[N],id[N],Tree[N*],n;
#define ls (node<<1)
#define rs (node<<1|1)
void updata(int node){
Tree[node]=Tree[ls]+Tree[rs];
}
void change(int l,int r,int node,int p)
{
if(l>p || r<p)return ;
if(l==p && r==p)
{
Tree[node]++;
return ;
}
int mid=(l+r)>>;
change(l,mid,ls,p);
change(mid+,r,rs,p);
updata(node);
}
int getsum(int l,int r,int node,int sa,int se)
{
if(l>se || r<sa)return ;
if(sa<=l && r<=se)return Tree[node];
int mid=(l+r)>>;
return getsum(l,mid,ls,sa,se)+getsum(mid+,r,rs,sa,se);
}
int mt(int x)
{
int l=,r=n,mid;
while(l<=r)
{
mid=(l+r)>>;
if(b[mid]==x)return mid;
if(b[mid]>x)r=mid-;
else l=mid+;
}
return -;
}
int head[N],num=,ans[N];
struct Lin{
int next,to;
}a[N];
void init(int x,int y){
a[++num].next=head[x];
a[num].to=y;
head[x]=num;
}
void dfs(int x)
{
int tmp=getsum(,n,,id[x]+,n);
for(int i=head[x];i;i=a[i].next)dfs(a[i].to);
ans[x]=getsum(,n,,id[x]+,n)-tmp;
change(,n,,id[x]);
}
int main()
{
n=gi();
int x;
for(int i=;i<=n;i++)val[i]=b[i]=gi();
sort(b+,b+n+);
for(int i=;i<=n;i++)id[i]=mt(val[i]);
for(int i=;i<=n;i++)x=gi(),init(x,i);
dfs();
for(int i=;i<=n;i++)printf("%d\n",ans[i]);
return ;
}