【bzoj4756】[Usaco2017 Jan]Promotion Counting 离散化+树状数组_weixin_30609331的博客-程序员宅基地

原文地址:http://www.cnblogs.com/GXZlegend/p/6832263.html


题目描述

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…N1…N (1≤N≤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 ii has a distinct proficiency rating, p(i), which describes how good she is at her job. If cow ii is an ancestor (e.g., a manager of a manager of a manager) of cow jj, then we say jj is a subordinate of ii.
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 ii in the company, please count the number of subordinates jj where p(j)>p(i).
n只奶牛构成了一个树形的公司,每个奶牛有一个能力值pi,1号奶牛为树根。
问对于每个奶牛来说,它的子树中有几个能力值比它大的。

输入

The first line of input contains N
The next N lines of input contain the proficiency ratings p(1)…p(N) 
for the cows. Each is a distinct integer in the range 1…1,000,000,000
The next N-1 lines describe the manager (parent) for cows 2…N 
Recall that cow 1 has no manager, being the president.
n,表示有几只奶牛 n<=100000
接下来n行为1-n号奶牛的能力值pi
接下来n-1行为2-n号奶牛的经理(树中的父亲)

输出

Please print N lines of output. The ith line of output should tell the number of 
subordinates of cow ii with higher proficiency than cow i.
共n行,每行输出奶牛i的下属中有几个能力值比i大

样例输入

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

样例输出

2
0
1
0
0


题解

离散化+树状数组

先将数据离散化,然后在树上dfs。

搜子树之前求一下比w[x]小的数的个数,搜子树之后再求一下比w[x]小的数的个数,作差即为子树中比w[x]小的数的个数。最后把w[x]加入到树状数组中。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
struct data
{
	int w , id;
}a[N];
int n , v[N] , pos[N] , f[N] , ans[N] , head[N] , to[N] , next[N] , cnt;
void add(int x , int y)
{
	to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;
}
bool cmp(data a , data b)
{
	return a.w < b.w;
}
void update(int x , int a)
{
	int i;
	for(i = x ; i <= n ; i += i & -i) f[i] += a;
}
int query(int x)
{
	int i , ans = 0;
	for(i = x ; i ; i -= i & -i) ans += f[i];
	return ans;
}
void dfs(int x)
{
	int i;
	ans[x] -= query(v[x]);
	for(i = head[x] ; i ; i = next[i]) dfs(to[i]);
	ans[x] += query(v[x]);
	update(v[x] , 1); 
}
int main()
{
	int i , x;
	scanf("%d" , &n);
	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i].w) , a[i].id = i;
	sort(a + 1 , a + n + 1 , cmp);
	for(i = 1 ; i <= n ; i ++ ) v[a[i].id] = n - i + 1;
	for(i = 2 ; i <= n ; i ++ ) scanf("%d" , &x) , add(x , i);
	dfs(1);
	for(i = 1 ; i <= n ; i ++ ) printf("%d\n" , ans[i]);
	return 0;
}

转载于:https://www.cnblogs.com/GXZlegend/p/6832263.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30609331/article/details/99218944

智能推荐

5千和2万,普通程序员和熟练开发者的差别_foruok的博客-程序员宅基地

从技术能力的角度,看普通程序员的薪水和熟练开发者为什么相差4、5倍。

poj 3067 Japan(线段树 | 树状数组)_gg_gogoing的博客-程序员宅基地_poj - 3067线段树

题意:有M个城市到N个城市修高速,问这个过程会有多少个交叉点?这道题和Stars很像,基本一个模型。在纸上画一画会发现,按照一个(小到大)顺序下来,交点的个数是以另一边为数组,大于该数把所有路按照以东海岸变为起点u,西海岸为终点v保存下来。然后按照u从小到大顺序排序(v的顺序不重要)。排完序之后,依次枚举就相当于从西海岸的城市1开始依次开始建立连接一直到n为止。当处理到第i条边时,

程序员客栈 接不到单子_常见(但不常见)单子_dfsgwe1231的博客-程序员宅基地

程序员客栈 接不到单子 上周,我们研究了Monad如何帮助您实现Haskell开发的下一个飞跃。 我们讨论了runXXXT模式,以及如何使用其余代码中的某些monad作为通用网关。 但是有时它也有助于回到基础知识。 实际上,我花了很长时间才真正掌握如何使用几个基本的monad。 或者至少,我不了解如何将它们用作单子。 在本文中,我们将研究如何使用列表monad和函数monad。 列表和...

html转PDF并添加水印_immaqi的博客-程序员宅基地_openhtmltopdf 水印

html导出pdf文章很多,但就是没有即用html转pdf又可以加水印的方法,研究了一整天,总算搞定了。详细见代码先看效果HTML内容template_freemarker_watermark.html&lt;!DOCTYPE html&gt;&lt;html lang="en"&gt;&lt;head&gt; &lt;meta charset="UTF-8"/&gt; &lt;title&gt;Title&lt;/title&gt; &lt;style&gt;

PTA-6-10 二分查找 (20分)-C语言_Alexling0的博客-程序员宅基地_6-10 二分查找 (15 分)c

本题要求实现二分查找算法。函数接口定义:Position BinarySearch( List L, ElementType X );其中List结构定义如下:typedef int Position;typedef struct LNode *List;struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */};L是用户传入的一个线性表,其中ElementTy

mini2440开发板LCD背光灯驱动移植_lifengxun20121019的博客-程序员宅基地

开发板中,LCD背光是通过 CPU的 LCD_PWR引脚来控制的,当 LCD_PWR 输出为高电平“1”时,将打开背光;当输出为低电平“0”时,将关闭背光(注意:这里只是打开和关闭背光,而并没有背光亮度的调节作用)。我们需要增加一个简单的背光驱动,以便能够通过软件便可简单的控制背光的开关。我们要达到的目的是:在命令终端通过向背光设备发送偶数比如“0”便可关闭背光,发送奇数比如“1”便可打开

随便推点

Java一维数组的练习题_「已注销」的博客-程序员宅基地

从键盘输入学生的人数 和成绩并选取最大值,为学生的成绩进行划分等级等级如下:①成绩与最高分差十分及以内 level=A ②成绩与最高分差二十分及以内 level=B ③成绩与最高分差三十分及以内 level=C ④其他 level=D代码如下...

centos7下yum安装与安装包(离线)安装redis_PAIverson的博客-程序员宅基地_centos7 redis离线安装

安装redisYum安装检查是否有redis yum 源yum install redis下载fedora的epel仓库yum install epel-release安装redis数据库yum install redis安装完毕后,使用下面的命令启动redis服务启动redisservice redis start停止redisservice redis stop查看r...

07-伪元素和伪类选择器_风轻雨扬的博客-程序员宅基地

伪元素和伪类选择器伪元素选择器:first-letter 和 :first-line:before 和 :afterCSS3新增的伪类选择器结构性伪类选择器UI元素伪类选择器:target伪类选择器:not 伪类选择器伪元素选择器  伪元素选择器并不是针对真正的元素使用的选择器,伪元素选择器只能针对CSS中已有的伪元素起作用。:first-letter 和 :first-line:first-letter: 该选择器对应的CSS样式对指定对象内的第一个字符起作用:first-line: 该选择器

使用 nodejs 写爬虫(一): 常用模块和 js 语法_余腾靖的博客-程序员宅基地

常用模块常用模块有以下几个:fs-extrasuperagentcheeriolog4jssequelizechalkpuppeteerfs-extra使用 async/await 的前提是必须将接口封装成 promise, 看一个简单的例子:const sleep = (milliseconds) =&gt; { return new Promise((reso...

ES6语法新特性_向天再借500年的博客-程序员宅基地_es6语法新特性

ES6语法新特性为什么要学习 ES6let 关键字不允许重复声明块儿级作用域(局部变量):不存在变量提升:不影响作用域链:let案例:点击div更改颜色应用场景const 关键字声明必须赋初始值:不允许重复声明:值不允许修改:块儿级作用域(局部变量):应用场景:变量和对象的解构赋值应用场景:模板字符串应用场景:简化对象和函数写法为什么要学习 ES6ES6 的版本变动内容最多,具有里程碑意义;ES6 加入许多新的语法特性,编程实现更简单、高效;ES6 是前端发展趋势,就业必备技能;let 关键字

设计模式---代理(Proxy)模式_honor_zhang的博客-程序员宅基地_proxy设计模式

1 定义代理模式,为想要访问的对象创建一个代理,使访问原对象变为访问代理对象。代理模式可以提供非常好的访问控制。生活中最多的代理模式例子就是中介。2 代理模式结构与实现代理模式通用类图如下所示:Subject 抽象主题角色:可以是抽象类,也可以是接口。抽象主题是一个普通的业务类型,无特殊要求。 RealSubject 具体主题角色:也叫做被委托角色或被代理角色,是业务逻辑的具体执行者。 Proxy 代理主题角色:也叫做委托类或代理类。它负责对真实角色的应用,把所有抽象主题.

推荐文章

热门文章

相关标签