[BOJ 7578] 공장 (C++)

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

7578번: 공장

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll *tree;
vector<pair<int,int> > v;

ll query(int left, int right, int node, int queryLeft, int queryRight){
    if (right<queryLeft || queryRight<left){
        return 0;
    }
    else if (queryLeft<=left && right<=queryRight){
        return tree[node];
    }
    else{
        int mid=(left+right)/2;
        return query(left, mid, node*2, queryLeft, queryRight)+query(mid+1, right, node*2+1, queryLeft, queryRight);
    }
}  

void update(int left, int right, int node, int machine_num){
    if (left<=machine_num && machine_num<=right){
        tree[node]+=1;
        if (left!=right){
            int mid=(left+right)/2;
            update(left, mid, node*2, machine_num);
            update(mid+1, right, node*2+1, machine_num);
        }
    }
}

bool compare(pair<int,int> a, pair<int,int> b){
    return a.second<b.second;
}

int binarySearch(int target, int start, int end){
    while (start<=end){
        int mid=(start+end)/2;
        if (v[mid].second<target){
            start=mid+1;
        }
        else if (v[mid].second>target){
            end=mid-1;
        }
        else{
            return v[mid].first;
        }
    }
    return 0;
}

int main(){
    int N, x, S=1;
    ll ans=0;
    cin>>N;
    int machines[N+1];
    for (int i=1; i<=N; i++){
        cin>>x;
        v.push_back(make_pair(i,x));        //first: 인덱스 second: 머신넘버
    }
    sort(v.begin(), v.end(), compare);
    for (int i=1; i<=N; i++){
        cin>>x;
        machines[i]=binarySearch(x,0,N-1);
    }
    while (S<N){
        S*=2;
    }
    tree=new ll[S*2];
    memset(tree, 0, sizeof(ll)*(S*2));
    for (int i=1; i<=N; i++){
        ans+=query(1,S,1,machines[i]+1,N); //count bigger number than me so far
        update(1,S,1,machines[i]);
    }
    delete[] tree;
    cout<<ans<<"\n";
    return 0;
}

말해뭐해.. 역시나 플래티넘답게 어려움.

첨에 접근방식을 잘못해서 인덱스드 트리를 쓰긴 썼는데 mintree, maxtree 따로 만들고 조건따져서 sum..했는데 답이 다 이상하게 나왔다.. 결국 힌트 참고..

 

[구현 방법]

1,2,3,4,5

2,4,1,3,5

 

이렇게 있으면 자기 기준으로 왼쪽에 있는 수들이 자기보다 크면 케이블이 발생한다는 아이디어.

그래서 인덱스드 트리를 이용해 자기(i)보다 큰 애들 [i+1, N] 의 수를 세주면 된다. 그리고 자기가 연결될 때 인덱스드 트리를 +1 씩(자기가 속한 구간에 한해 모두) 증가시켜주면 된다.

아이디어를 떠올리고-이걸 인덱스드 트리와 연결하는 과정이 중요했다.

 

그리고 map으로 인덱스를 지정하니 TLE 발생. pair로 인덱스,머신번호 묶어줘서 정렬한 뒤 이분탐색으로 해결했다.(백준 큐앤에이 참고했다)