【题目链接】

点击打开链接

【算法】

离散化 + dfs + 树状数组

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000 int N,i,lth,x,pos;
int a[MAXN+],tmp[MAXN+],rank[MAXN+],ans[MAXN+];
vector<int> E[MAXN+]; template <typename T> inline void read(T &x) {
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
} template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
} template <typename T> inline void writeln(T x) {
write(x);
puts("");
} struct BinaryIndexedTree {
int bit[MAXN+];
int lowbit(int x) { return x & -x; }
inline void modify(int pos) {
int i;
for (i = pos; i <= N; i += lowbit(i)) bit[i]++;
}
inline int query(int pos) {
int i,ret = ;
for (i = pos; i; i -= lowbit(i)) ret += bit[i];
return ret;
}
} BIT; inline void dfs(int x) {
int i;
BIT.modify(rank[x]);
ans[x] = -BIT.query(rank[x]-);
for (i = ; i < E[x].size(); i++) dfs(E[x][i]);
ans[x] += BIT.query(rank[x]-);
} int main() { read(N);
for (i = ; i <= N; i++) {
read(a[i]);
tmp[i] = a[i];
} sort(tmp+,tmp+N+);
for (i = ; i <= N; i++) {
if (tmp[i] != tmp[i-])
tmp[++lth] = tmp[i];
} for (i = ; i <= N; i++) {
pos = lower_bound(tmp+,tmp+lth+,a[i]) - tmp;
rank[i] = N - pos + ;
} for (i = ; i <= N; i++) {
read(x);
E[x].push_back(i);
} dfs(); for (i = ; i <= N; i++) writeln(ans[i]); return ; }

最新文章

  1. C和指针 第十五章 输入输出缓冲
  2. Java中List,ArrayList、Vector,map,HashTable,HashMap区别用法
  3. 浩瀚先森(guohao1206.com)
  4. 2016-03-10:libx265源码解析
  5. Integral类型的跨平台使用
  6. 【转】Android用NDK和整套源码下编译JNI的不同
  7. 69个微信小程序常见问题
  8. JQuery插件使用之Validation 快速完成表单验证的几种方式
  9. rails4 new没有生成prototype.js之类的脚本解决办法
  10. Java设计模式系列-装饰器模式
  11. linux安装elk
  12. SLES Install
  13. ubuntu18.04安装redis
  14. 使用异步任务降低API延迟_实践总结
  15. Golang--选择、循环语法总结
  16. bigdata-01-应用
  17. 初学CSS-1-CSS的格式
  18. 批处理--批量打开程序&amp;批量关闭程序
  19. BZOJ 1011 [HNOI2008]遥远的行星 (误差分析)
  20. 注册表:DWORD

热门文章

  1. ubuntu下用webbench做网站压力测试
  2. NIO与传统IO的区别(形象比喻)[转]
  3. flask生成环境不要使用其自身低性能的服务器
  4. RNN与LSTM
  5. [转】 nginx rewrite规则
  6. Answer&amp;#39;s Question about pointer
  7. BUPT复试专题—字符串处理(2016)
  8. 静态NAT、动态NAT、PAT(端口多路复用)的配置
  9. 【Discuz】ucenter通讯失败与Discuz的头像无法显示
  10. iOS 获取appstore 版本