[洛谷 3605][USACO17JAN]Promotion Counting

题目链接

https://www.luogu.com.cn/problem/P3605

题解

统计一个数组中权值大于（小于）某个数的数量可以用权值树状数组实现。

可以通过这样的算法来统计：

1. 遍历到一个点 \(u\) 时，先统计已经遍历过的点中（这些点都在子树外）权值大于 \(p_u\) 的点的数量。
2. DFS 遍历这个点的所有子树。
3. 遍历完这棵子树后，权值树状数组已经存了子树外的点和子树内的点（除了当前点）的所有数据，因此可以统计出这些点中权值大于 \(p_u\) 的点的数量，用它减去子树外的数量即为子树内的数量。
4. 将当前点插入权值树状数组。

因为权值值域较大，需要预先离散化。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int p[100005],np[100005],ans[100005],tot,n;
vector<int> e[100005];
struct bit
{
 int n,s[100005];
 void init(int N)
 {
  n=N;
 }
 int lowbit(int x)
 {
  return x&(-x);
 }
 void add(int x,int y)
 {
  while(x<=n)
  {
   s[x]+=y;
   x+=lowbit(x);
  }
 }
 int sum(int x)
 {
  int ans=0;
  while(x)
  {
   ans+=s[x];
   x-=lowbit(x);
  }
  return ans;
 }
}tr;
void dfs(int u)
{
 ans[u]-=(tr.sum(n)-tr.sum(p[u]));
 for(auto v:e[u])
  dfs(v);
 ans[u]+=(tr.sum(n)-tr.sum(p[u]));
 tr.add(p[u],1);
}
int main()
{
 cin>>n;
 tr.init(n);
 for(int i=1;i<=n;i++)
  cin>>np[i],p[i]=np[i];
 sort(np+1,np+n+1);
 for(int i=1;i<=n;i++)
  p[i]=lower_bound(np+1,np+n+1,p[i])-np;
 for(int i=2;i<=n;i++)
 {
  int fa;
  cin>>fa;
  e[fa].push_back(i);
 }
 dfs(1);
 for(int i=1;i<=n;i++)
  cout<<ans[i]<<endl;
 return 0;
}