C++14(g++5.4) 解法, 执行用时: 50ms, 内存消耗: 6104K, 提交时间: 2019-08-09 15:13:35

#include<algorithm>
#include<cstdio>
#define Re register int
#define F(a,b) for(i=a;i<=b;++i)
const int N=1e5+3;
int x,i,n,t,C[N],Q[N],ip[N],ans[N],nex[N],head[N];
struct A{int x,i;bool operator<(A b)const{return x<b.x;};}a[N];
inline void add(Re x,Re y){Q[++t]=y,nex[t]=head[x],head[x]=t;}
inline void in(Re &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
inline void addx(Re x){while(x<=n)++C[x],x+=x&(-x);}
inline int ask(Re x){int ans=0;while(x)ans+=C[x],x-=x&(-x);return ans;}
inline void dfs(Re x){
    ans[x]-=ask(n)-ask(ip[x]);
    for(Re i=head[x];i;i=nex[i])dfs(Q[i]);
    ans[x]+=ask(n)-ask(ip[x]);
    addx(ip[x]);
}
int main(){
    in(n);
    F(1,n)in(a[i].x),a[i].i=i;
    std::sort(a+1,a+n+1);
    F(1,n)ip[a[i].i]=i;
    F(2,n)in(x),add(x,i);
    dfs(1);
    F(1,n)printf("%d\n",ans[i]); 
}

C++11(clang++ 3.9) 解法, 执行用时: 87ms, 内存消耗: 6556K, 提交时间: 2019-07-01 21:30:36

#include<cstdio>
#include<algorithm>
#define F(i,a,b) for(int i=a;i<=b;++i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
int n,q;
int a[100001],O[100001],Ans[100001],b[100001];
inline void I(int x){for(;x<=n;++b[x],x+=x&-x);}
inline int Q(int x){int sum=0;for(;x;sum+=b[x],x-=x&-x);return sum;}
int h[100001],nxt[100001],to[100001],tot;
inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;}
inline bool cmp(int p1,int p2){return a[p1]>a[p2];}
void dfs(int u){
    Ans[u]=-Q(a[u]);
    eF(i,u) dfs(to[i]);
    Ans[u]+=Q(a[u]);
    I(a[u]);
}
int main(){
    scanf("%d",&n);
    F(i,1,n) scanf("%d",a+i), O[i]=i;
    std::sort(O+1,O+n+1,cmp);
    F(i,1,n) a[O[i]]=i;
    int x;
    F(i,2,n) scanf("%d",&x), ins(x,i);
    dfs(1);
    F(i,1,n) printf("%d\n",Ans[i]);
    return 0;
}