【USACO2017JAN】 Promotion Counting
2024-08-30 12:43:06
【题目链接】
【算法】
离散化 + 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 ; }
最新文章
- C和指针 第十五章 输入输出缓冲
- Java中List,ArrayList、Vector,map,HashTable,HashMap区别用法
- 浩瀚先森(guohao1206.com)
- 2016-03-10:libx265源码解析
- Integral类型的跨平台使用
- 【转】Android用NDK和整套源码下编译JNI的不同
- 69个微信小程序常见问题
- JQuery插件使用之Validation 快速完成表单验证的几种方式
- rails4 new没有生成prototype.js之类的脚本解决办法
- Java设计模式系列-装饰器模式
- linux安装elk
- SLES Install
- ubuntu18.04安装redis
- 使用异步任务降低API延迟_实践总结
- Golang--选择、循环语法总结
- bigdata-01-应用
- 初学CSS-1-CSS的格式
- 批处理--批量打开程序&;批量关闭程序
- BZOJ 1011 [HNOI2008]遥远的行星 (误差分析)
- 注册表:DWORD
热门文章
- ubuntu下用webbench做网站压力测试
- NIO与传统IO的区别(形象比喻)[转]
- flask生成环境不要使用其自身低性能的服务器
- RNN与LSTM
- [转】 nginx rewrite规则
- Answer&;#39;s Question about pointer
- BUPT复试专题—字符串处理(2016)
- 静态NAT、动态NAT、PAT(端口多路复用)的配置
- 【Discuz】ucenter通讯失败与Discuz的头像无法显示
- iOS 获取appstore 版本