7578

문제를 푸는것 자체는 별로 어렵지 않았다. 

부분합 문제를 변형한 형태이기 때문에 그 점을 잘 파악해서 풀면 된다. 가장 왼쪽에 있는 기기 부터 전선을 하나씩 이어가며 교차점의 수를 늘려간다.

교차점의 수를 찾는 방법은 가장 오른쪽으로 떨어진 지점까지 현결된 전선의 개수와 현재의 위치에서 기계와 연결된 지점 까지의 전선 개수를 빼면 된다. 

가장 오른쪽으로 떨어진 점 까지의 연결된 전선의 개수는 교차 가능성이 있는 전선들이고 연결된 지점의 왼쪽에 있는 전선의 개수는 교차 가능성이 없는 전선들이기 때문에 둘의 차는 해당 지점에서 전선을 연결 했을 때 교점과 같다.

알고리즘은 쉽게 생각했는데 내가 틀렸던 이유는 교차점의 수가 int의 범위를 넘을 수 있다는 것을 생각하지 못했기 때문이다... 이미 틀려버린 3 문제가 정말 억울하다...

교차점은 0+1+2+...+499999까지 생기는데 이러면 int범위를 거뜬히 넘어버린다

앞으로 결과의 자료형은 왠만하면 long long을 사용해야겠다.

#include<iostream> #include<cstdio> using namespace std; #define MaxVal 500005 int tree[500005+1]; int local[1000005]; int read(int idx) { int sum = 0; while(idx > 0){ sum += tree[idx]; idx -= (idx & -idx); } return sum; } void update(int idx, int val) { while(idx <= MaxVal) { tree[idx] += val; idx += (idx & -idx); } } int main() { int N, tmp, tc; int a, b, c; long long res=0; int base=0; scanf("%d", &N); for(int i = 1; i <= N; i++){ scanf("%d", &tmp); local[tmp]=i; } for(int i=1; i<=N; i++){ scanf("%d", &tmp); base = max(base, max(i,local[tmp])); res += read(base) - read(local[tmp]); update(local[tmp], 1); } printf("%lld\n", res); return 0; }