BZOJ4756 - [Usaco2017 Jan]Promotion Counting

本文主要是介绍BZOJ4756 - [Usaco2017 Jan]Promotion Counting，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Portal

Description

给出一个\(n(n\leq10^5)\)个点的带点权的以\(1\)为根的树，求每个点的子树中有多少个权值比该点大的点。

Solution

线段树合并。
我们对于每一个点\(u\)，建立一棵线段树保存子树\(u\)中的所有权值。那么\(ans_u\)就等于线段树中比\(val_u\)大的值有多少。而子树\(u\)中的所有权值等于\(u\)的所有子节点的子树中的权值加上\(val_u\)，那么想要构建出\(u\)的线段树，只要将\(son_u\)的线段树全部合并起来再加上\(val_u\)就好啦。注意以上所说的线段树都是要动态开点的。
如何合并两棵线段树呢？我们递归的去合并线段树中的每一个位置。merge(p1,p2)返回合并节点\(p_1\)和\(p_2\)之后得到的节点，看代码就很容易理解啦。

时间复杂度\(O(nlogn)\)。

Code

//[Usaco2017 Jan]Promotion Counting
#include <algorithm>
#include <cstdio>
using namespace std;
inline char gc()
{static char now[1<<16],*s,*t;if(s==t) {t=(s=now)+fread(now,1,1<<16,stdin); if(s==t) return EOF;}return *s++;
}
inline int read()
{int x=0; char ch=gc();while(ch<'0'||'9'<ch) ch=gc();while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();return x;
}
const int N=1e5+10;
int n,val[N]; int ans[N];
int n0,map[N];
void discrete()
{for(int i=1;i<=n;i++) map[i]=val[i];sort(map+1,map+n+1); n0=unique(map+1,map+n+1)-map-1;for(int i=1;i<=n;i++) val[i]=lower_bound(map+1,map+n0+1,val[i])-map;n0++; //有可能会询问max+1
}
int cnt,h[N];
struct edge{int v,nxt;} ed[N];
void edAdd(int u,int v) {cnt++; ed[cnt].v=v,ed[cnt].nxt=h[u],h[u]=cnt;}
const int Ns=3e6+10;
int sgCnt,rt[N],ch[Ns][2],sum[Ns];
void update(int p) {sum[p]=sum[ch[p][0]]+sum[ch[p][1]];}
void ins(int &p,int L0,int R0,int x)
{if(!p) p=++sgCnt;if(x<=L0&&R0<=x) {sum[p]++; return;}if(!p) p=++sgCnt;int mid=L0+R0>>1;if(x<=mid) ins(ch[p][0],L0,mid,x);else ins(ch[p][1],mid+1,R0,x);update(p);
}
int query(int &p,int L0,int R0,int L)
{if(!p) p=++sgCnt;if(L<=L0) return sum[p];int mid=L0+R0>>1; int res=0;if(L<=mid) res+=query(ch[p][0],L0,mid,L);res+=query(ch[p][1],mid+1,R0,L);return res; 
}
int merge(int p1,int p2)
{if(!p1||!p2) return !p1?p2:p1;ch[p1][0]=merge(ch[p1][0],ch[p2][0]);ch[p1][1]=merge(ch[p1][1],ch[p2][1]);sum[p1]+=sum[p2];return p1;
}
void dfs(int u)
{ins(rt[u],1,n0,val[u]);for(int i=h[u];i;i=ed[i].nxt){int v=ed[i].v;dfs(v); rt[u]=merge(rt[u],rt[v]);}ans[u]=query(rt[u],1,n0,val[u]+1);
}
int main()
{n=read();for(int i=1;i<=n;i++) val[i]=read();discrete();for(int i=2;i<=n;i++) edAdd(read(),i);dfs(1);for(int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0;
}