【题意】带点权树,统计每个结点子树内点权比它大的结点数。
【算法】线段树合并
【题解】对每个点建权值线段树(动态开点),DFS中将自身和儿子线段树合并后统计。
注意三个量tot,cnt,tots,细心查错。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
int n,first[maxn],cnt,tot,tots,root[maxn],a[maxn],b[maxn],ans[maxn];
struct edge{int v,from;}e[maxn*];
void ins(int u,int v){tots++;e[tots].v=v;e[tots].from=first[u];first[u]=tots;}
struct cyc{int l,r,sum;}t[maxn*];
void insert(int l,int r,int &x,int y){
if(!x)x=++cnt;t[x].sum++;
if(l==r)return;//
int mid=(l+r)>>;
if(y<=mid)insert(l,mid,t[x].l,y);
else insert(mid+,r,t[x].r,y);
}
int merge(int x,int y){
if(!x||!y)return x^y;//
t[x].l=merge(t[x].l,t[y].l);
t[x].r=merge(t[x].r,t[y].r);//
t[x].sum=t[t[x].l].sum+t[t[x].r].sum;//
return x;
}
int ask(int left,int right,int k,int l,int r){
if(l<=left&&right<=r)return t[k].sum;
else{
int mid=(left+right)>>,sum=;
if(l<=mid)sum=ask(left,mid,t[k].l,l,r);
if(r>mid)sum+=ask(mid+,right,t[k].r,l,r);
return sum;
}
}
void dfs(int x){
insert(,tot,root[x],a[x]);
for(int i=first[x];i;i=e[i].from){
dfs(e[i].v);
root[x]=merge(root[x],root[e[i].v]);
}
if(a[x]<tot)ans[x]=ask(,tot,root[x],a[x]+,tot);
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
for(int i=;i<=n;i++){
int fa;scanf("%d",&fa);
ins(fa,i);
}
sort(b+,b+n+);tot=n;
tot=unique(b+,b+tot+)-b-;
for(int i=;i<=n;i++)a[i]=lower_bound(b+,b+tot+,a[i])-b;
dfs();
for(int i=;i<=n;i++)printf("%d\n",ans[i]);
return ;
}