문제 보기
한동안 쉬운 문제들에 대한 블로그 글 작성은 의미가 없다는 생각에 접어두고 있었다.
그리고 요즘 플래를 건드리기 시작했다.
막상 풀다보니 또 못 풀것도 아니다 라고 말하고 싶지만 지금 2문제차라 자만은 접어두고...(뭐래)

문제 이해

교차점을 세야한다.
일단 딱 보고서, 조합론적인 접근을 생각해본다.
하지만 간선의 연결 방법에 따라 엄청 다양하므로 정형화된 공식 같은거는 없을 것이란 걸 직감할 수 있다.

그러면, 단순한 관찰..!

line intersect 체크 아이디어를 떠올리자.
간선 기준으로 다른 간선의 양 끝점이 서로 반대편에 위치하면 "교차"한다고 판별한다.

윗배열을 A, 아랫배열을 B라고 생각하자.
A의 첫 인덱스를 기준으로 (B의 식별번호 인덱스)-1이 간선 위에서 교차점의 수가 된다는 것을 알 수 있다. 왜냐면 전부 A의 첫 인덱스 뒤쪽으로 간선이 이어질 것이기 때문이다.
(말이 잘 이해가 안 된다면 언제든 댓글)

그러면 A에서 앞에서부터 하나씩 꺼내가면서 B의 어떤 값들을 찾아가면 될 것 같다.
여기까지가 대충 밑그림이다.

계획하기

아 근데 B배열의 어떤 값은 최초에 (인덱스)-1을 가진다.
하지만, 처리하고 나면 더 이상 사용되지 않으므로 B 배열에서 사용한 인덱스의 뒤쪽 값들은 전부 -1이 되어야 할 것이다.
"전부"... 빠르게 처리하려면?
그렇다 세그-점 쿼리/구간 업뎃이다!
나도 말만 들어봤는데 딱 이거다 싶어 책 보면서 구현해봤다.
다행히 이 방향이 맞았다. 개꿀

코드

A 배열은 문제와 다소 독립적임을 강조하기 위해 ranged-base for문을 사용했다.
id[i]으로 나타냈다.
B 배열은 정의역이 식별번호이다. 그래서 order의 약자로 ord[id[i]]가 B 배열의 인덱스를 나타내도록 설정했다. 마지막 for문에서는 ord[k]가 되었다.
밥먹고올게요

#include <iostream>
#include <tuple>
#define REP(i,a,b) for (int i = a; i <= b; ++i)
using namespace std; void solve(); int main() {ios::sync_with_stdio(0); cin.tie(0); solve();}
using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>;

const int N = 524290, M = 1000003;
int n, tree[N<<1], ord[M];

void update(int t, int x, iii node = {1,1,n}) {
    auto [k,l,r] = node;
    if (t < l || r < t) return;
    if (l == r) {tree[k] += x; return;}
    int m = (l+r)>>1;
    update(t,x,{k<<1,l,m}); update(t,x,{(k<<1)|1,m+1,r});
    tree[k] = tree[k<<1]+tree[(k<<1)|1];
} void update(ii range, int x) {
    auto [s,e] = range;
    update(s,x);
    update(e+1,-x);
}

auto query(int t, iii node = {1,1,n}) {
    auto [k,l,r] = node;
    if (t-1 < l || r < 1) return tree[0];
    if (1 <= l && r <= t-1) return tree[k];
    int m = (l+r)>>1;
    return query(t,{k<<1,l,m})+query(t,{(k<<1)|1,m+1,r});
}

void solve() {
    cin >> n;
    int id[n];
    for (auto& s : id) cin >> s;
    REP(i,1,n) {
        int x; cin >> x;
        ord[x] = i;
        update({i,n},1);
    }
    ll ans = 0;
    for (auto k : id) {
        ans += query(ord[k]);
        update({ord[k],n},-1);
    }
    cout << ans;
}