BZOJ4756:[USACO]Promotion Counting(线段树合并)

Description

n只奶牛构成了一个树形的公司，每个奶牛有一个能力值pi，1号奶牛为树根。
问对于每个奶牛来说，它的子树中有几个能力值比它大的。

Input

n，表示有几只奶牛 n<=100000
接下来n行为1-n号奶牛的能力值pi
接下来n-1行为2-n号奶牛的经理（树中的父亲）

Output

共n行，每行输出奶牛i的下属中有几个能力值比i大

Sample Input

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

Sample Output

2
0
1
0
0

Solution

线段树合并模板题，$DFS$一遍，然后把儿子的线段树合并到自己身上，查询比自己能力值大的有多少个。

Code

 #include<iostream>

 #include<cstdio>

 #define N (100009)

 #define INF (1000000000)

 using namespace std;

 struct Sgt{int ls,rs,val;}Segt[N<<];

 struct Edge{int to,next;}edge[N<<];

 int n,x,sgt_num,a[N],ans[N],Root[N];

 int head[N],num_edge;

 void add(int u,int v)

 {

     edge[++num_edge].to=v;

     edge[num_edge].next=head[u];

     head[u]=num_edge;

 }

 void Update(int &now,int l,int r,int x)

 {

     if (!now) now=++sgt_num;

     Segt[now].val++;

     if (l==r) return;

     int mid=(l+r)>>;

     if (x<=mid) Update(Segt[now].ls,l,mid,x);

     else Update(Segt[now].rs,mid+,r,x);

 }

 int Query(int now,int l,int r,int l1,int r1)

 {

     if (l>r1 || r<l1) return ;

     if (l1<=l && r<=r1) return Segt[now].val;

     int mid=(l+r)>>,ls=Segt[now].ls,rs=Segt[now].rs;

     return Query(ls,l,mid,l1,r1)+Query(rs,mid+,r,l1,r1);

 }

 void Merge(int &x,int y)

 {

     if (!x || !y) {x|=y; return;}

     Segt[x].val+=Segt[y].val;

     Merge(Segt[x].ls,Segt[y].ls);

     Merge(Segt[x].rs,Segt[y].rs);

 }

 void DFS(int x,int fa)

 {

     for (int i=head[x]; i; i=edge[i].next)

         if (edge[i].to!=fa)

         {

             DFS(edge[i].to,x);

             Merge(Root[x],Root[edge[i].to]);

         }

     ans[x]=Query(Root[x],,INF,a[x]+,INF);

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=; i<=n; ++i)

     {

         scanf("%d",&a[i]);

         Update(Root[i],,INF,a[i]);

     }

     for (int i=; i<=n; ++i)

     {

         scanf("%d",&x);

         add(i,x); add(x,i);

     }

     DFS(,);

     for (int i=; i<=n; ++i)

         printf("%d\n",ans[i]);

 }