P3605 [USACO17JAN]Promotion Counting P
2021/10/21 23:39:23
本文主要是介绍P3605 [USACO17JAN]Promotion Counting P,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Jennie
和常规的求逆序对差不多
在从根节点往下走的时候,我们必须要避免不在他子树内的点的影响
那就先减去他们呗。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; template<class T> void read(T &now){ now=0; char c=getchar(); int f=1; while((!isdigit(c))){ if(c=='-') f=-1; // cout<<isdigit(c)<<" "<<c<<" "; c=getchar(); } while(isdigit(c)){ now=(now<<1)+(now<<3)+c-'0'; c=getchar(); } now*=f; } int n; int b[1000005]; int p[1000005]; int head[1000005]; int ans[1000005]; struct e{ int to; int ne; }ed[1000005]; int x; int pp; void add(int f,int to){ ed[++pp].to=to; ed[pp].ne=head[f]; head[f]=pp; } int ma; int lowbit(int x){ return x&-x; } int tr[1000005]; void addd(int x,int k){ for(int i=x;i<=n;i+=lowbit(i)){ tr[i]+=k; } } int qu(int x){ int ans=0; while(x){ ans+=tr[x]; x-=lowbit(x); } return ans; } void dfs(int x){ ans[x]-=(qu(n)-qu(p[x])); for(int i=head[x];i;i=ed[i].ne){ dfs(ed[i].to); } ans[x]+=(qu(n)-qu(p[x])); addd(p[x],1); //cout<<qu(n)<<endl; } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ read(b[i]); p[i]=b[i]; } sort(b+1,b+n+1); for(int i=1;i<=n;++i){ p[i]=lower_bound(b+1,b+n+1,p[i])-b; } for(int i=2;i<=n;++i){ read(x); add(x,i); } dfs(1); for(int i=1;i<=n;++i){ printf("%d\n",ans[i]); } return 0; }
这篇关于P3605 [USACO17JAN]Promotion Counting P的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding