我就搞不懂了，明明标签一大堆，做法那么多，为什么题解区里就这么几种做法呢？

一篇 pbds 平衡树启发式合并题解，清晰易懂，代码简短。

题意

一棵有根树，点有点权，问每个点的子树中权值大于它的个数。

解法

显然地，暴力做法中，如果我们知道所有儿子权值的集合，直接 lowerbound 查排名即可。

那我们直接从下向上用平衡树存即可，显然下面已经遍历过的点直接释放即可，空间 $O(n)$。

但是直接合并时间会炸，随便一棵树就可以卡满，于是想到启发式合并。

借鉴树链剖分中重儿子的概念，我们把一个点的儿子中，sz 最大的称为重儿子。合并时直接继承重儿子，将其他儿子合并即可。

时间复杂度 $O(n \log^2 n)$，由于常数小，跑得比一般线段树合并快。

Code

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
const int N=1e5+5;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> Tree;
int n,m;
int w[N];
int fa[N];
int ans[N];
vector<int> g[N];
int son[N],sz[N];
void dfs2(int u){
	sz[u]=1;
	for(int v:g[u]){
		dfs2(v);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])
			son[u]=v;
	}
	return;
}
void dfs(int u,Tree& s){
	Tree t;
	if(son[u])	dfs(son[u],t);
	t.insert(w[u]);
	for(int v:g[u]){
		if(v==son[u])	continue;
		Tree c;
		dfs(v,c);
		for(int x:c)
			t.insert(x);
	}
	ans[u]=sz[u]-t.order_of_key(w[u]);
	s.swap(t);
	return;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	for(int i=2;i<=n;i++){
		cin>>fa[i];
		g[fa[i]].push_back(i);
	}
	dfs2(1);
	Tree rt;
	dfs(1,rt);
	for(int i=1;i<=n;i++)
		cout<<ans[i]-1<<'\n';
	return 0;
}

C87 树状数组+DFS P3605 [USACO17JAN] Promotion Counting P

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,w[N],b[N],ans[N],c[N];
vector<int> G[N];
void add(int x,int k){ for(;x<=n;x+=x&-x)c[x]+=k;}
int sum(int x){ int res=0;for(;x>=1;x-=x&-x)res+=c[x];return res;}
void dfs(int x)
{
    int t=( sum(n)-sum(w[x]) );//原来比x强的

    for(int y:G[x])dfs(y);
        
    ans[x]=( sum(n)-sum(w[x]) ) -t ;//后来比x强的
    
    add(w[x],1);
}
int main() 
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d",&w[i]),b[i]=w[i];
    sort(b+1,b+n+1);
    for(int i=1; i<=n; i++)w[i]=lower_bound(b+1,b+n+1,w[i])-b;

    for(int i=2,x; i<=n; i++)scanf("%d",&x),G[x].push_back(i);

    memset(ans,0,sizeof(ans));
    memset(c,0,sizeof(c));
    dfs(1);

    for(int i=1; i<=n; i++)printf("%d\n",ans[i]);

    return 0;
}