1615. 교차개수세기

1615번: 교차개수세기

---

뭔가 많이 본 듯한 문제이다. 어디서 봤나 했더니 2568번 전깃줄 문제와 매우 유사하다. 물론 풀이가 유사하다는 건 아니고 그림이 비슷하다는 소리. 이 문제에서는 전깃줄이 교차하는 횟수를 세어야 한다.

 

문제에 두 전깃줄이 교차하는 조건이 주어져 있는데, 계산의 편의를 위해 왼쪽에 있는 정점을 오름차순으로 살펴보면서, 각 정점의 전깃줄이 다른 전깃줄과 몇 번 교차하는지 계산해 보자. 

 

왼쪽 정점 $i$와 오른쪽 정점 $j$에 연결된 전깃줄을 $(i, ~j)$이라고 하자. 전깃줄 $(i,~j)$에 대해 $a < i$이고 $b > j$인 전깃줄 $(a,~b)$의 개수를 세어야 한다. $a > i$인 경우를 세지 않는 이유는 정점을 오름차순으로 보고 있기 때문이다.

 

당연히 매번 모든 간선을 탐색하면 안 된다. 그러면 총 시간복잡도가 $O(M^{2})$인데 $M$이 최대 $N^{2}$이므로 $O(N^{4})$에 푸는 셈이다. 말이 안 된다.

 

그러면 어떻게 해야 하느냐.. 주어진 전깃줄을 표로 나타내 보자.

행과 열은 각각 왼쪽 정점과 오른쪽 정점을 나타낸다.

 

다시 한 번 식을 살펴보면, 전깃줄 $(i,~j)$에 대해 $a < i$이고 $b > j$인 전깃줄 $(a,~b)$의 개수를 세어야 한다. 예를 들어 전깃줄 $(3,~2)$에 대해 탐색해야 하는 영역은 다음과 같다.

전깃줄 $(5, ~3)$의 영역은 다음과 같다.

일반화하면 전깃줄 $(i,~j)$에 대해 $[1,~j+1] \times [i-1,~n]$ 영역의 합을 구하면 된다. 이 값은 2차원 부분합으로 쉽게 계산할 수 있다. 부분합을 계산하는 데 $O(N^{2})$, 각 간선에 대해 부분합을 얻는 데 $O(M)$ 시간이 걸리므로 총 $O(N^{2})$ 시간에 문제를 풀 수 있다.

---

참고로 long long 써야 한다. 흑흑