思路
线段树合并的板子。。
和子节点合并之后在值域线段树上查询即可代码
#include#include #include using namespace std;const int MAXN = 1000100;int n,Nodecnt,root[MAXN],u[MAXN<<1],v[MAXN<<1],cnt,fir[MAXN],nxt[MAXN<<1],ans[MAXN],ax[MAXN],w_p[MAXN],nx;struct Node{ int lson,rson,sz;}Seg[MAXN<<2];int merge(int x,int y,int l,int r){ if(x*y==0) return x+y; if(l==r){ int t=++Nodecnt; Seg[t].sz=Seg[x].sz+Seg[y].sz; return Nodecnt; } int g=++Nodecnt; Seg[g].sz=Seg[x].sz+Seg[y].sz; int mid=(l+r)>>1; Seg[g].lson=merge(Seg[x].lson,Seg[y].lson,l,mid); Seg[g].rson=merge(Seg[x].rson,Seg[y].rson,mid+1,r); return g;}int query(int l,int r,int o,int val){ if(l==r){ return 0; } int mid=(l+r)>>1; if(val<=mid) return query(l,mid,Seg[o].lson,val)+Seg[Seg[o].rson].sz; else return query(mid+1,r,Seg[o].rson,val);}void build(int l,int r,int &o,int val){ if(!o) o=++Nodecnt; Seg[o].sz++; if(l==r) return; int mid=(l+r)>>1; if(val<=mid) build(l,mid,Seg[o].lson,val); else build(mid+1,r,Seg[o].rson,val);}void addedge(int ui,int vi){ ++cnt; u[cnt]=ui; v[cnt]=vi; nxt[cnt]=fir[ui]; fir[ui]=cnt;}void dfs(int u,int fa){ for(int i=fir[u];i;i=nxt[i]){ if(v[i]==fa) continue; dfs(v[i],u); root[u]=merge(root[v[i]],root[u],1,n); } ans[u]=query(1,n,root[u],w_p[u]);}void init(void){ sort(ax+1,ax+n+1); nx=unique(ax+1,ax+n+1)-ax-1;// printf("%d\n",nx); for(int i=1;i<=n;i++){ w_p[i]=lower_bound(ax+1,ax+nx+1,w_p[i])-ax;// printf("%d!\n",w_p[i]); } for(int i=1;i<=n;i++){ build(1,n,root[i],w_p[i]); }} int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&w_p[i]),ax[i]=w_p[i]; } for(int i=2;i<=n;i++){ int x; scanf("%d",&x); addedge(i,x); addedge(x,i); } init(); dfs(1,0); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0;}