백준 15957번 - 음악 추천

https://www.acmicpc.net/problem/15957

15957번: 음악 추천

 

• 필요한 배경지식

병렬 이분 탐색(PBS), 펜윅 트리, 오일러 경로 테크닉

 

 

 

• 문제 해결 방법

[1,N] 번 노래를 부른 가수의 평균 점수가 J를 넘게 되는 시간을 각각 구하기 위해, 주워지는 쿼리를 이용하여 병렬 이분 탐색을 할 수 있습니다.

 

특정 노래를 부른 가수의 평균점수가 J점수를 언제 초과하는지 확인하기 위해 쿼리를 매개변수로 이분탐색을 하는데 이를 N개의 노래에 대하여 병렬로 탐색을 수행하면 됩니다.

 

탐색할때 쿼리를 업데이트하거나 노래의 점수를 확인하기 위해서는 펜윅트리나 lazy propagation을 이용한 세그먼트 트리를 이용할 수 있습니다.

 

주의할 점은 같은 가수가 부른 곡은 같은 결과값을 가지므로 병렬 이분 탐색을 수행할때 중복되는 계산을 방지해 주어야 합니다.

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
#define MAX_N 100000
#define MAX_Q 100000
using namespace std;
using tpi = tuple<int,int,int>;
using ll = long long;

int N,Q;
ll J;
vector<int> adj[MAX_N+1]{};
vector<int> songs[MAX_N+1]{};
vector<tpi> qu;
int singer[MAX_N+1]{};
ll tree[MAX_N+1]{};
int in[MAX_N+1]{}, out[MAX_N+1]{};
int st[MAX_Q+1]{}, ed[MAX_Q+1]{};
int vi[MAX_N+1]{};
ll sAvg[MAX_N+1]{};

ll query(int idx){
    ll ret = 0;
    while(idx > 0){
        ret += tree[idx];
        idx -= (idx & -idx);
    }
    return ret;
}
void update(int idx, ll diff){
    while(idx < MAX_N+1){
        tree[idx] += diff;
        idx += (idx & -idx);
    }
}

int num = 0;
void dfs(int now){
    in[now] = ++num;
    for(auto next : adj[now])
        dfs(next);
    out[now] = num;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>Q;
    cin>>J;
    int t;
    for(int i=2; i<=N; i++){
        cin>>t;
        adj[t].push_back(i);
    }
    dfs(1);
    for(int i=1; i<=N; i++){
        cin>>t;
        songs[t].push_back(i);
        singer[i] = t;
    }

    int T,P,S;
    qu.push_back({-1,-1,-1});
    for(int i=1; i<=Q; i++){
        cin>>T>>P>>S;
        qu.push_back({T,P,S});
    }
    sort(qu.begin(), qu.end());
    fill(st, st+N+1, 1);
    fill(ed, ed+N+1, Q);
	
    while(1){
        vector<vector<int>> pbs(Q+1);
        int maxMid = 0;
        for(int i=1; i<=N; i++){ // song
            if(st[i] <= ed[i]){
                int mid = (st[i] + ed[i])>>1;
                pbs[mid].push_back(i);
                maxMid = max(maxMid, mid);
            }	
        }
        if(maxMid==0) break;

        memset(tree,0,sizeof(tree));
        memset(vi,0,sizeof(vi));
        for(int q=1; q<=maxMid; q++){
            tie(T,P,S) = qu[q];
            S /= (out[P] - in[P] + 1);
            update(in[P], S);
            update(out[P]+1, -S);
            for(auto nsong : pbs[q]){
                int nsinger = singer[nsong];
                ll &avg = sAvg[nsinger];
                if(vi[nsinger] != q){
                    vi[nsinger] = q;
                    ll sum = 0;
                    for(auto nsong : songs[nsinger]){
                        sum += query(in[nsong]);
                    }
                    avg = sum / songs[nsinger].size();
                    if(sum%songs[nsinger].size()!=0) avg++;
                }
                
                if(avg > J) ed[nsong] = q - 1;
                else st[nsong] = q + 1;
            }
        }
    }

    for(int i=1; i<=N; i++){
        int idx = st[i];
        if(idx > Q) cout<<-1<<'\n';
        else cout<<get<0>(qu[idx])<<'\n';
    }

}