脚本宝典收集整理的这篇文章主要介绍了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("%dn",ans[i]);
}
return 0;
}
以上是脚本宝典为你收集整理的P3605 [USACO17JAN]Promotion Counting P全部内容,希望文章能够帮你解决P3605 [USACO17JAN]Promotion Counting P所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。