[백준 7578번] [세그먼트 트리 / 스위핑] 공장

Approach

Inversion counting임을 파악하고 병합정렬을 활용해서 풀어줄 수도 있다.

 

잘 생각해보면, B의 i번째 위치에 놓인 점에 의해 교차점이 발생하는 횟수는 자기보다 먼저 대응된 것 중에 자신보다 큰 것의 개수와 같다.

이렇게 되면, i번째 위치에 놓인 점의 이동 횟수를 구하는 시점에 자신보다 숫자가 큰 것의 개수만 구한 것과 B의 i ~ inf번째 위치에 놓인 것 중 대응된 것의 개수를 구하는 것이 동치가 된다.

 

예를 들어, a의 i번쨰 수가 B에 대응되는 index가 $b_{a_i}$라고 할 떄, 결과적으로 해당 선에 의해 교차점이 생기는 상황은 $b_{a_i}$부터 50000(inf) 위치 사이에 놓인 대응된 점의 개수와 동치이다.

https://viyoung.tistory.com/393와 접근 방법이 거의 유사하다.

[백준 2336번] [세그먼트 트리 / 스위핑] 굉장한 학생