P3605 [USACO17JAN]Promotion Counting P

题意：

大概是给定一个有\(n\)个节点的树，每个节点都有个权值\(p[i]\)，需要求出每个节点的逆序对，逆序对当且仅当该点比其子节点的数大，问每个节点有几对逆序对？(\(n\leq10^5,p[i]\leq10^9\))

题解：

我们遍历每个节点，先减去已经插入树状数组中的逆序对，因为已经插入的不是他的子节点不记录答案，然后遍历子节点，最后再加上此时树状数组中的逆序对，然后再插入该节点就可以了。

#include "bits/stdc++.h"
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],ans[N],c[N];
vector<int>v[N];
int lowbit(int x){
	return x&-x;
}
void add(int x){
	while(x<=n){
		c[x]++;
		x+=lowbit(x);
	}5
}
int query(int x){
	int ans=0;
	while(x){
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}
void dfs(int u){
	ans[u]-=query(n)-query(a[u]);
	for(auto to:v[u]){
		dfs(to);
	}
	ans[u]+=query(n)-query(a[u]);
	add(a[u]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=n;i++)	b[i]=a[i];
	for(int i=2;i<=n;i++){
		int x;cin>>x;
		v[x].push_back(i);
	}
	sort(b+1,b+1+n);
	int len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)	
	a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	dfs(1);
	for(int i=1;i<=n;i++)	cout<<ans[i]<<"\n";
	return 0;
} 

P3605 [USACO17JAN]Promotion Counting P

原文：https://www.cnblogs.com/monster-Z/p/14392672.html