我们用树状数组做差就可以解决一切问题,我用桶排并用此来表示出第几大就可以直接求前缀和了

#include<cstdio>
#include<algorithm>
#define MAXN 100010
using namespace std;
inline int read()
{
int sum=;
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<='')
{
sum=(sum<<)+(sum<<)+ch-'';
ch=getchar();
}
return sum;
}
int P[MAXN],H[MAXN];
int n,m;
struct VIA
{
int to,next;
}c[MAXN];
int head[MAXN],t;
inline void add(int x,int y)
{
c[++t].to=y;
c[t].next=head[x];
head[x]=t;
}
inline int sum_H(int x)
{
int sum=;
while(x>) sum+=H[x],x-=x&(-x);
return sum;
}
inline int sum_P(int x)
{
int sum=;
while(x>) sum+=P[x],x-=x&(-x);
return sum;
}
inline void ins_P(int x,int key)
{
while(x<=n) P[x]+=key,x+=x&(-x);
}
inline void ins_H(int x,int key)
{
while(x<=n) H[x]+=key,x+=x&(-x);
}
int a[MAXN],pos[MAXN];
int Ans[MAXN][];
int comp(const int x,const int y)
{
return a[x]>a[y];
}
inline void Init()
{
scanf("%d",&n);
for(int i=,x;i<=n;i++)x=read(),add(x,i);
for(int i=;i<=n;i++)a[i]=read(),pos[i]=i;
sort(pos+,pos+n+,comp);
for(int i=;i<=n;i++)a[pos[i]]=i;
}
void dfs(int x)
{
ins_H(a[x],);
int y=sum_H(a[x]-);
Ans[x][]=sum_P(a[x]-);
ins_P(a[x],);
for(int i=head[x];i;i=c[i].next)
dfs(c[i].to);
Ans[x][]=sum_H(a[x]-)-y;
ins_P(a[x],-);
Ans[x][]=a[x]--Ans[x][];
}
inline void work()
{
dfs();
for(int i=;i<=n;i++)
printf("%d %d %d\n",Ans[i][],Ans[i][],Ans[i][]);
}
int main()
{
Init();
work();
return ;
}

最新文章

  1. Android课程---如何用网格视图做出手机桌面APP
  2. 对于git的认识
  3. 常见.NET功能代码汇总
  4. (转)Sublime Text 2 2.0.2 序列号
  5. HDU 4727 The Number Off of FFF 2013年四川省赛题
  6. [置顶] think in java interview番外篇-谈程序员如何修练英语
  7. 历峰集团3.43亿美元收购Net-a-Porter剩余股权_财经_腾讯网
  8. inner join on, left join on, right join on
  9. nyoj 过河问题
  10. Dynamics 365 CE命令栏按钮点击后刷新表单页面方法
  11. LVS-DR模式 SOP
  12. Mysql哪些字段适合建立索引
  13. Maven报错Please ensure you are using JDK 1.4 or above and not a JRE解决方法!
  14. java 线程Thread 技术--1.5Lock 与condition 演示生产者与消费模式
  15. Hadoop3集群搭建之——虚拟机安装
  16. 使用matlibplot.pyplot设置画图的坐标系
  17. BLE资料应用笔记 -- 持续更新(转载)
  18. 《王者荣耀》技术总监复盘回炉历程:没跨过这三座大山,就是另一款MOBA霸占市场了
  19. Java基础之断言
  20. [二叉树建树]1119. Pre- and Post-order Traversals (30) (前序和后序遍历建立二叉树)

热门文章

  1. RubyMine常用快捷键
  2. 001---Linux系统的启动过程
  3. Python3爬虫(八) 数据存储之TXT、JSON、CSV
  4. Python3乘法口诀表(由上至下+由下至上)
  5. Python tips(
  6. Uber:中国市场两年内不考虑盈利,每年补贴10亿美金
  7. 类 java.util.Collections 提供了对Set、List、Map进行排序、填充、查找元素的辅助方法。
  8. Django笔记 —— 模型高级进阶
  9. Linux系统学习笔记(1)
  10. 「日常训练」 Soldier and Number Game (CFR304D2D)