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;
} 
上一篇:UVA1225Digit Counting


下一篇:备份的优化和调整