[백준 7578] 공장 (C++)

문제 링크: https://www.acmicpc.net/problem/7578

7578번: 공장

1. 주의할 점

- 세그먼트트리 혹은 펜윅트리에 대해 알고 있어야 한다

- 답의 경우, 구간합의 합이므로 LongLong으로 설정한다

 

2. 구현

- 서로 다른 두 선분이 만나서 생기는 교차점의 수를 구한다 → 첫째 행에서 둘째 행으로 선분을 잇는다 → 둘째행 기준 오른쪽에 이미 연결된 선분의 수만큼 교차한다 → 오른쪽에 연결된 선분의 수를 구간합으로 구한다 → 연결된 둘째행의 인덱스가 포함된 트리에는 +1을 수행한다

- 첫째 행을 First[]에, 둘째 행을 Second[]에 저장한다. 단, Second는 100만의 배열을 할당하여 해당 숫자가 두번째 행에서 몇 번째에 위치하는지 저장한다

- 첫째행의 가장 왼쪽부터 시작한다

- 첫째행과 연결된 둘째행의 인덱스를 Arrive에 저장한다

- 세그먼트 트리의 경우, (Arrive,Num] 중에서 연결된 점들의 수를 구하여 Result에 더한다. 이후, Update를 통해 Arrive 또한 이미 연결된 지점이라는 표시를 수행한다

- 펜윅트리의 경우, Arrive를 연결된 지점으로 설정한다. 이후, 현재 Node까지 연결된 선분 수 - [1,Arrive] 를 통해 (Arrive,Num]를 구한다

 

[세그먼트 트리]

#include <iostream>
#include <cmath>
using namespace std;
int first[500001];
int second[1000001];
long long *tree;

long long sum(int node, int start, int end, int left, int right){
    if(left>end || right<start) return 0;
    if(left<=start && end<=right) return tree[node];
    int mid = start + (end-start)/2;
    return sum(node*2,start,mid,left,right) + sum(node*2+1,mid+1,end,left,right);
}

void update(int node, int start, int end, int idx){
    if(start<=idx && idx<=end){
        tree[node]+=1;
        if(start!=end){
            int mid = start + (end-start)/2;
            update(node*2,start,mid,idx);
            update(node*2+1,mid+1,end,idx);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,height,val;
    long long result=0;
    cin>>num;
    height = ceil(log2(num));
    tree = new long long[1<<(height+1)];
    for(int i=1;i<=num;i++)
        cin>>first[i];
    for(int i=1;i<=num;i++){
        cin>>val;
        second[val] = i;
    }
    for(int i=1;i<=num;i++){
        int arrive = second[first[i]];
        long long tmp = sum(1,1,num,arrive+1,num);
        result+=tmp;
        update(1,1,num,arrive);
    }
    cout<<result;
    return 0;
}

 

[펜윅트리]

#include <iostream>
#include <cmath>
using namespace std;
int first[500001];
int second[1000001];
long long tree[500001];
int num,val;
long long result=0;

long long sum(int idx){
    long long temp = 0;
    while(idx){
        temp+=tree[idx];
        idx = idx - (idx & -idx);
    }
    return temp;
}

void update(int idx){
    while(idx<=num){
        tree[idx]+=1;
        idx = idx + (idx & -idx);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>num;
    for(int i=1;i<=num;i++)
        cin>>first[i];
    for(int i=1;i<=num;i++){
        cin>>val;
        second[val] = i;
    }
    for(int i=1;i<=num;i++){
        int arrive = second[first[i]];
        update(arrive);
        result += (i-sum(arrive));
    }
    cout<<result;
    return 0;
}