[7578번] 공장

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리 :: http://www.crocus.co.kr/648

2. Map STL :: http://www.crocus.co.kr/604

세그트리와 Map을 써야하는 문제이다.

이 문제의 알고리즘을 그림으로 모두 설명해 보려한다.

A를 기준으로 케이블을 확인해본다.

A의 132번 케이블은 B의 3번째에 존재한다.

처음 케이블이 들어온 것이기에 현재는 0이다.

방문을 하였다면 B의 3번을 1로 표시해주는 과정이다.

이제 A의 392를 보면 B의 1번째에 있다.

이 1번째는 A의 처음 케이블이 생성된 132와 교차하게 된다.

그 과정이 tree[3]이 1이기에 1개 케이블이 교차한다는 것을 알 수 있다.

이제 B의 1번째도 1로 표시해준다.

A의 311은 B의 4번째이다.

아직 B의 1, 3번째만 케이블이 생겼으므로 교차하는 것이 없다(A의 351은 아직 케이블이 없다고 생각한다.)

B의 4번째도 1로 표시해준다.

이제 A의 351은 B의 2번째이다.

이 351 케이블이 생성되자 마자 132, 311과 교차하게 된다.

그것이 tree[3], tree[4]가 1이기에 확인 할 수 있게 되는 것이다.

B의 2번째를 1로 표시해준다.

이렇게 교차하는 수를 확인할 수 있는 방법을 그림으로 설명해 보았다.

이때 왜 Map을 쓰냐면, A의 value로 B에서의 Index를 찾기 위해서 쓰는 것이고

왜 세그먼트 트리를 쓰냐면 누적합을 알고있어야 하기 때문이다.

그렇지 않으면 Tree[k] + Tree[k+1] + ... + Tree[n]까지 for문으로 구해야 하기 때문이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
 
using namespace std;
 
typedef long long ll;
 
int tree[500002];
int n;
 
void update(int i)
{
    while (i <= n)
    {
        tree[i] += 1;
        i += (i & -i);
    }
}
 
int sum(int i)
{
    int ans = 0;
    while (i > 0)
    {
        ans += tree[i];
        i -= (i & -i);
    }
    return ans;
}
 
int main()
{
    scanf("%d", &n);
 
    vector<int> vcA;
    for (int i = 1; i <= n; i++)
    {
        int val;
        scanf("%d", &val);
 
        vcA.push_back(val);
    }
 
    map<int, int> B;
    for (int i = 1; i <= n; i++)
    {
        int val;
        scanf("%d", &val);
 
        B[val] = i;
    }
 
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        int valA = vcA[i];
        int idxB = B[valA];
 
        ans += (ll)sum(n) - (ll)sum(idxB);
 
        update(idxB);
    }
 
    printf("%lld", ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>