Promotion Counting P

Promotion Counting P

首先离散化

我们可以从大到小排序，

对于每一个节点，我们需要统计它的子树中比它大的节点的个数

然后建一棵权值树状数组，在递归子树之前先把大于他的减掉，递归完子树后再把新的答案加回来

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100005;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
int n;
int p[N],b[N];
bool cmp(int a,int b){return p[a]>p[b];}
int hd[N],nxt[N<<1],to[N<<1],tot;
inline void add(int x,int y) {
    to[++tot]=y;nxt[tot]=hd[x];hd[x]=tot;
}
int ans[N],c[N];
void upd(int x) {
    for(int i=x;i<=n;i+=i&(-i))
        c[i]++;
}
int query(int x) {
    int res=0;
    for(int i=x;i;i-=i&(-i))
        res+=c[i];
    return res;
}   
void dfs(int x) {
    ans[x]=-query(p[x]);
    for(int i=hd[x];i;i=nxt[i]) 
        dfs(to[i]);
    ans[x]+=query(p[x]);
    upd(p[x]);
}
int main() {
    n=read();
    for(int i=1;i<=n;i++) p[i]=read(),b[i]=i;
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++) p[b[i]]=i;
    for(int i=2,x;i<=n;i++) 
        x=read(),add(x,i);
    dfs(1);
    for(int i=1;i<=n;i++)
        printf("%d
",ans[i]);
    return 0;
}
/*
首先离散化
我们可以从大到小排序，
对于每一个节点，我们需要统计它的子树中比它大的节点的个数
然后建一棵权值树状数组，在递归子树之前先把大于他的减掉，递归完子树后再把新的答案加回来
*/