능력주의 회사 (JUNGOL 3998)

https://jungol.co.kr/problem/3998?cursor=MTMsMCw5

---

아이디어

i의 자식이면서 p값이 더 큰것의 개수를 세어주면 됩니다. 이때 p값의 범위가 너무 크므로 값 압축을 이용하여 1이상 100,000 이하의 수로 바꾸어줍시다. 그리고 DFS를 돌리면서 i번 노드에 들어갈 때까지 지나간 정점중 p값이 i의 p값보다 큰 정점의 개수를 저장해줍니다. 그리고 i번 노드의 DFS를 나올때까지 지나간 정점중 p값이 i의 p값보다 큰 정점의 개수를 저장해줍니다. 이 두 값의 차이가 i의 자식이면서 p값이 더 큰 정점의 개수입니다.

 

이와같은 쿼리는 세그먼트 트리를 이용해주면 해결해줄 수 있습니다.

---

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll N;
ll tree[404040]={0};
void update(ll s,ll e,ll node,ll idx,ll val)
{
    if (idx<s || e<idx) return;
    tree[node]+=val;
    if (s==e) return;

    ll mid=(s+e)/2;
    update(s,mid,node*2,idx,val);
    update(mid+1,e,node*2+1,idx,val);
}
ll Sum(ll s,ll e,ll node,ll l,ll r)
{
    if (e<l || r<s) return 0;
    if (l<=s && e<=r) return tree[node];
    ll mid=(s+e)/2;
    return Sum(s,mid,node*2,l,r)+Sum(mid+1,e,node*2+1,l,r);
}

ll Num[101010]={0};
vector <ll> v[101010];
ll Ans[101010]={0};

void DFS(ll node)
{
    update(1,N,1,Num[node],1);
    Ans[node]-=Sum(1,N,1,Num[node]+1,N);
    for (ll next:v[node])
        DFS(next);
    Ans[node]+=Sum(1,N,1,Num[node]+1,N);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll i;
    vector <ll> nums;

    cin>>N;
    for (i=1;i<=N;i++)
    {
        cin>>Num[i];
        nums.push_back(Num[i]);
    }
    sort (nums.begin(),nums.end());
    for (i=1;i<=N;i++)
        Num[i]=lower_bound(nums.begin(),nums.end(),Num[i])-nums.begin()+1;

    for (i=2;i<=N;i++)
    {
        ll x;
        cin>>x;
        v[x].push_back(i);
    }

    DFS(1);

    for (i=1;i<=N;i++)
        cout<<Ans[i]<<"\n";
}