题意:
大概是给定一个有\(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;
}