BOJ 7578 공장

문제

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

문제를 변형해보면 "Inverse의 수를 세는 문제"로 바꿀 수 있다.

 

풀이

세그먼트 트리나 BIT 를 사용할 때 많은 경우에 좌표 압축하여 해싱 느낌으로 사용한다.

 

Inverse 의 수를 셀 때도 각 값을 볼때마다, 자기 전에 나온것들 중, 자신보다 큰 것들의 갯수를 카운팅 해준다.

 

각 수를 인덱스로 하는 배열을 생각해 보면, 각 수를 볼때마다

1. arr[i]~n 까지의 칸들중 등장한 칸의 개수를 세어 준다. -> arr[i]~n 구간의 합을 구한다.

2. arr[i]번 칸에 체크를 해 준다 -> arr[i] 칸에 1을 업데이트 해준다.

 

두 연산 모두 BIT 연산으로 처리 가능하다.

 

시간복잡도 : $O(NlogN)$

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;
const int MAXNUM = 1e6;

int n, arr[MAXN+10], M[MAXNUM+10];
ll ans;

struct BIT
{
    int n; vector<int> tree;
    BIT(int n) : n(n), tree(n+10) {}
    void update(int i) { for(; i<=n; i+=(i&-i)) tree[i]++; }
    int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
};

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d", &n);
    for(i=1; i<=n; i++) { int x; scanf("%d", &x); M[x]=i; }
    for(i=1; i<=n; i++) { int x; scanf("%d", &x); arr[i]=M[x]; }

    BIT bit(n);
    for(i=1; i<=n; i++)
    {
        ans+=bit.query(n)-bit.query(arr[i]);
        bit.update(arr[i]);
    }
    printf("%lld", ans);
    return 0;
}