7585번: 공장

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


$O(n\lg n)$

아래 기계를 하나씩 추가하되 위쪽에 연결된 기계도 하나씩 추가해보자.
교차점의 개수는 추가하는 기계와 연결되어 있는 위쪽의 기계 뒤에 있는 기계들의 수를 누적한 값이다.
이 문제를 빠르게 해결하기 위해 bit를 사용한다.
처음 위 기계들의 번호를 입력받을 때 순서대로 그 기계 번호에 몇 번째로 입력받은 기계인지 저장해놓는다.
아래 기계들의 번호를 입력받을 때는 해당 기계와 연결된 기계 번호 & bit를 적절히 사용하여 문제를 해결한다.

#include<stdio.h>
const int MAX_N = 5e5, MAX_L = 1e6;
int bit[MAX_N + 1], idx[MAX_L + 1], n;
long long r;
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), idx[x] = i;
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        for (int j = idx[x]; j <= n; j += j&-j) r += bit[j];
        for (int j = idx[x]; j; j -= j&-j) bit[j]++;
    }
    printf("%lld", r);
    return 0;
}